Project Euler 204

プロジェクトオイラー
http://projecteuler.net/index.php

Q204.
100以下の素因数のみ持つ10⁹以下の自然数の個数。

ただ素数で割って、再帰を使うだけ。2で割った数の同様の個数と、3で割った数の同様の個数（ただし、3以上しか因数に使えない）と、...、97で（略）の個数を足し合わせる。1も別途足す。

def is_prime(n):

    for p in primes:

        if p * p > n:

            return True

        elif n % p == 0:

            return False

    return True
def make_primes(limit):

    for n in range(3, limit + 1, 2):

        if is_prime(n):

            primes.append(n)
def num_harmonic(n, i = 0):

    if n < primes[i]:

        return 1

    

    s = 1

    for k in range(i, len(primes)):

        p = primes[k]

        if p > n:

            break

        s += num_harmonic(n / p, k)

    return s
N = 100

M = 10 ** 9

primes = [ 2 ]

make_primes(N)

print num_harmonic(M)