Project Euler Problem 27
数学的にいくつか工夫をすると、だいぶ探索数が減らせる。
- 二次式にn=0を代入すれば、そもそもb自身が素数でであることはすぐにわかる。
- n=bの時は式全体はbの倍数である。よって、どんなにがんばってもn=b-1までしか連続した素数は得られない。よって、n=bの時は素数判定は必要ない。
という2点が主な工夫。これ以外にもあるかもしれないけど、すぐに思いつかなかった。2.37秒という
Pythonスクリプトとしては速いような遅いような微妙な速度で処理が終わったので、良いことにした。
#!/usr/bin/python # -*- coding: utf-8 -*- primes = set() # 素数集合 compos = set() # 合成数集合 0は便宜上合成数 def init_prime(n): global primes for i in range(3,n,2): for p in primes: if i % p == 0: break else: primes.add(i) def is_prime(n): global primes,compos n = abs(n) if n in primes: return True if n in compos: return False for p in primes: if n % p == 0: compos.add(n) return None primes.add(n) return True def get_n_seq(a,b): n = 0 while True: if n >= b: break m = n**2 + a*n + b if is_prime(m): n += 1 else: break return n def main(): init_prime(1000) blist = list(primes) + [-p for p in primes] max_len= (0,0,0) # (n, a, b) for b in blist: for a in range(-999, 1000): n = get_n_seq(a,b) if n > max_len[0]: max_len = (n,a,b) print max_len print max_len[1] * max_len[2] main()