Project Euler Problem 047
http://projecteuler.net/index.php?section=problems&id=47
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2047
連続する2つの数がそれぞれ2つの異なる素因数を持つのは 14 = 2 × 7 15 = 3 × 5 の場合である. 同様に連続する3つの数がそれぞれ3つの異なる素因数を持つのは 644 = 22 × 7 × 23 645 = 3 × 5 × 43 646 = 2 × 17 × 19 の場合である. 連続する4つの数がそれぞれ4つの異なる素因数を持つ場合を考え, 連続する数の中で最小のものを答えよ.
分からなかったので無理くり解いた。すごく時間がかかる。
import math import itertools import datetime def primelist(limit=1000): checked = [ True ] * (limit/2) result = [2] for i in xrange(len(checked)): val = i * 2 + 3 if checked[i]: result.append(val) j = val + val + val while j < limit: checked[(j - 3) / 2] = False j += val + val return result pl = primelist(10000) def primefactors(n): result = [] limit = math.sqrt(n) for i in pl: while n % i == 0: result.append(i) n /= i limit = math.sqrt(n) if limit > n: break if n > 1: m = pl[-1] + 2 while n > 1 and m <= limit: while n % m: m += 2 else: while True: n /= m result.append(m) if n % m: break limit = math.sqrt(n) else: if n != 1: result.append(n) return result def euler047(): n = 4 def it(): for i in itertools.count(2): l = primefactors(i) if len(set(l)) != n: continue yield (i, l) p = 0 c = 1 checked = set() for i, l in it(): is_ok = False if i - 1 == p: b = [ (j, l.count(j)) for j in set(l) ] is_ok = True for j in b: if j in checked: is_ok = False break else: checked.add(j) if is_ok: c += 1 if c == n: print [ i-j+1 for j in xrange(n,0,-1) ] return else: if c != 1: checked = set() c = 1 p = i begin = datetime.datetime.now() euler047() end = datetime.datetime.now() print end - begin
答え: 134043 (134043, 134044, 134045, 134046)
実行時間: 1:12.490829秒くらい