Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-07-20

[][] Project Euler Problem 128 07:19 はてなブックマーク -  Project Euler Problem 128 - 練習帳

問題文

 no title

要約

 正六角形がハニカム構造で配置され,それぞれの正六角形の中をルールに従って数字を埋めていく(ルールは問題文の図を参照してください).ある数nに対し,nと隣接する書かれているそれぞれの数字(6個ある)と差の絶対値をとり,その中にある素数の個数をPD(n)で表す.PD(n)は常に3以下である事が示せるが,PD(n)=3となるnのうち2000番目に小さい数を答えよ.

方針

 1から見て真北方向にある数と,その数の右下に隣接する数しか条件を満たし得ません(それ以外は常に4個以上が合成数になる).それらを順々に調べていきます.

N = 2000
cnt = 0

def isprime(n):
    if n < 2:
        return False
    i = 2
    while(i*i <= n):
        if n%i == 0:
            return False
        i += 1     
    return True

n = 1
hit = []
while(cnt < N+2):
    if isprime(6*n-1) and isprime(6*n+1) and isprime(12*n+5):
        hit.append(2+3*(n-1)*n)
        cnt+=1
    if isprime(6*n-1) and isprime(6*n+5) and isprime(12*n-7):
        hit.append(1+3*n*(n+1))
        cnt+=1
    n+=1
print hit[N-1]