読者です 読者をやめる 読者になる 読者になる

「プライム・ペア」問題 

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

オイラーのφ関数 - 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)