Project Euler 179

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

Q179.
nとn+1の約数の個数が同じ1 < n < 10⁷の個数。

一つずつ約数の個数を求めてもいいが、それでは面白くないし、因数分解に時間がかかるので遅い。
約数の個数を格納する配列を作り、それを頭から見て、カウントする。まず、約数の個数に1をセットする。そして、2^eの倍数の約数の個数にe+1をかける。これを10^3.5までの素数に対して行う。その際に、別途nまでの配列を用意し、p^eの倍数なら、これで割っていく。そして、最後に1でなければ、10^3.5より大きい因子があることになるので、約数の個数に2をかける。

import time
def calc_exp(n, p):

    n /= p * p

    e = 2

    while n % p == 0:

        n /= p

        e += 1

    return e
def gen_primes(limit):

    p = 2

    while p <= limit:

        yield p

        while True:

            p += 1

            if a[p] == 1:

                break
t = time.clock()

N = 10 ** 7
a = [ 1 ] * (N + 1)

b = range(N + 1)

for p in gen_primes(int( (N + 0.5) ** 0.5)):

    for n in xrange(p, N + 1, p):

        if n % (p * p) == 0:

            e = calc_exp(n, p)

        else:

            e = 1

        a[n] *= e + 1

        b[n] /= p ** e

for i in xrange(N + 1):

    if b[i] > 1:

        a[i] *= 2
counter = 0

for n in range(2, N):

    if a[n] == a[n+1]:

        counter += 1

print counter
print time.clock() - t