Project Euler Problem 37
37以前で残してた問題もやってあるけど、大して面白いのが無いので省略
右(左)から1つずつ数字を取っていっても全て素数であるような数(11個しかない)の和を求めよ、という問題。
まず、それぞれの値の計算の仕方だが、これは簡単で、
- 右からの場合は、10で割っていけば良い
- 左からの場合は、10**log(n,10)での剰余をとれば良い
一応書くと、左から数字を取り去るには、 10を底としてlogを取ればその数字の桁数が取れるのでそれを利用する。
あと、高速化の工夫として、
ということで、ここまでの処理でPythonで2.01秒。Cで書くと10倍になると仮定すると0.2秒なので、まあいいことにする。
#!/usr/bin/python # -*- coding: utf-8 -*- from math import sqrt,log primes = set( (2,3,5,7) ) compos = set( (1,4,6,8,9,10) ) # 便宜上1を合成数として扱う def is_prime(n): global primes,compos if n in primes: return True if n in compos: return False for i in xrange(2, int(sqrt(n))+1): if n % i == 0: compos.add(n) return False primes.add(n) return True def is_ok(n): m = n # left to right while m > 0: if not is_prime(m): return False else: m %= (10**int(log(m,10))) # right to left m = n while m > 0: if not is_prime(m): return False else: m /= 10 return True count = 0 sum = 0 for n in xrange(11, 10000000): if (n % 10) not in (2,3,5,7) : continue if (n / 10**(int(log(n,10)))) not in (2,3,5,7): continue if is_ok(n): print n sum += n count += 1 if count >= 11: break print "count = %d, sum = %d" % (count, sum)