「プライム・ペア」問題

自然数 k に対し、1 から k までの自然数のうち k と互いに素なものの個数を F(k) と定義します。（F(k) はオイラーのΦ関数とも呼ばれています。参考：オイラーのφ関数（Wikipedia））

例えば F(12)＝4 です。1 から 12 のうち 12 と互いに素なのは 1, 5, 7, 11 の 4 つです。

標準入力から、自然数 n（1 ≦ n ≦ 105）が与えられます。標準出力に F(n！) を 1000003 で割った余りを出力するプログラムを書いてください。

例えば n＝10 のとき、F(10！)＝F(3628800)＝829440 です。同様に、F(20！) を 1000003 で割った値は 961998 です

求めるものはΦ(n!)でphi関数をバラすと n!Π_i (1-1/prime[i]) を計算すると (nまでの素数以外の積)(nまでの素数の積）とシンプルになるので、エラトステネスの篩でnまでの素数とそれ以外に分けて計算する。

def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False

def sieve(n):
    s = [True] * n
    for x in range(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in range(0,n) if s[i] and i > 1]


N=int(input())
primes=sieve(N+1)
not_primes=list(set(range(2,N+1))-set(sieve(N+1)))
mod=1000003

res=1
for i in not_primes: 
    res*=i
    res%=mod

for i in primes:
    res*=i-1
    res%=mod
    
print(res%mod)