本当は怖いHPC

HPC屋の趣味&実益ブログ

Project Euler Problem 37

37以前で残してた問題もやってあるけど、大して面白いのが無いので省略

右(左)から1つずつ数字を取っていっても全て素数であるような数(11個しかない)の和を求めよ、という問題。

まず、それぞれの値の計算の仕方だが、これは簡単で、

  • 右からの場合は、10で割っていけば良い
  • 左からの場合は、10**log(n,10)での剰余をとれば良い

一応書くと、左から数字を取り去るには、 10を底としてlogを取ればその数字の桁数が取れるのでそれを利用する。

あと、高速化の工夫として、

  • 素数判定は、既知の素数・合成数を全てキャッシュする
  • 最左桁、最右桁がそれぞれ2,3,5,7のいずれでもなければ即却下

ということで、ここまでの処理で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)

【広告】