「プライム・ペア」問題

prime_pair.rb

# phi関数の乗法性を用いる
# n!を素因数分解して、各素因数についてphi(p^e)を求めて掛け合わせる
# 階乗の素因数分解は良い求め方がある
# http://qiita.com/HirotoKagotani/items/87234e4104cb2b7fb8ff
#
# 累乗もmodで求めた方がいいかと思ったが、大丈夫だった

modulus = 1000003

# nまでの素数を配列に入れて返す
def prime_up_to(n)
    flags = [1] * (n + 1)
    flags[0] = 0
    flags[1] = 0
    flags.each_with_index do |x, i|
        if x == 1
            j = 2
            while i * j <= n
                flags[i * j] = 0
                j = j + 1
            end
        end
    end

    prime = []
    flags.each_with_index do |x, i|
        if x == 1
            prime.push(i)
        end
    end
    return prime
end

# 答えを求める関数
def euler_fact_mod(n, modulus)
    prime = prime_up_to(n)

    res = 1
    prime.each do |p|
        # 素因数分解の指数を求める
        quotient = n/p
        p_exp = 0
        while quotient > 0
            p_exp = p_exp + quotient
            quotient = quotient / p
        end
        # 公式でp-partを計算
        res = (res * ((p**p_exp) % modulus - (p**(p_exp - 1)) % modulus)) % modulus
    end

    return res
end

n = gets.to_i
puts euler_fact_mod(n, modulus)