Project Euler Problem 049
http://projecteuler.net/index.php?section=problems&id=49
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2049
項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ。 (i)3つの項はそれぞれ素数である。 (ii)各項は他の項の置換で表される。 1, 2, 3桁の素数にはこのような性質を持った数列は存在しないが、4桁の増加列にはもう1つ存在する。 それではこの数列の3つの項を連結した12桁の数を求めよ。
とくに工夫なし。
import math import datetime def is_prime(n): if n < 2: return False if n < 4: return True if n % 2 == 0: return False if n < 9: return True if n % 3 == 0: return False r = math.floor(math.sqrt(n)) f = 5 while f <= r: if n % f == 0: return False if n % (f+2) == 0: return False f += 6 return True def primelist(limit=1000): checked = [ True ] * ((limit-1)/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 def contain(n): result = [] while n: result.append(n%10) n /= 10 result.sort() return result def euler048(): primes = primelist(10000-6660) for i in primes: if i < 1000: continue if contain(i) == contain(i+3330) == contain(i+6660): if is_prime(i+3330) and is_prime(i+6660): print i, i+3330, i+6660 begin = datetime.datetime.now() euler048() end = datetime.datetime.now() print end - begin
答え: 296962999629
実行時間: 0.004150秒くらい