Project Euler #60 - prime pair sets

프로젝트 오일러 60번 - 소수짝 세트
3, 7, 109, 673은 각각 소수이면서, 두개씩 짝을 지어 붙여도 항상 소수가 된다. 예를 들어 7109, 1097 은 소수.
이런 성질을 만족하는 소수 5개짜리 세트.. 중 5개 숫자 합이 가장 작을 때?

지금까지 풀었던 문제 중에 가장 어려웠다. 계산 시간도 가장 오래 걸렸고.

4개짜리 세트를 만드는 데 673까지의 소수가 필요했으니.. 5개짜리 세트는 10배쯤 더 필요하지 않나..라고 추측해 본다.
일단 10,000까지의 소수를 모두 찾아둔다.
1200개 정도 되는 소수를 5개씩 묶는 방법은 1200^5 / 5! 너무 크다!
Partitioning해 보자. 3으로 나누어 1이 남는 소수들과 2가 남는 소수들로 나누어 볼 수 있다. 둘이 섞여 버리면 3의 배수가 되어 버리므로 10,000 이하 소수들을 다음과 같이 2개의 그룹으로 나누고, 각 그룹 안에서 5개짜리 세트를 찾으면 된다.
[3] + [x for x in primes_under_10000 if x%3 == 1]
[3] + [x for x in primes_under_10000 if x%3 == 2]

(설명이 좀 더 필요할 듯 하다. 각 자리수의 합이 3의 배수이면 이 수는 3의 배수가 되는 것은 모두 알 테고.. 각 자리수의 합이 3으로 나누어 1이 남는다는 것과 이 수를 3으로 나누었을 때 1이 남게 된다는 것은 동치이다. n 이 각 자리수의 합이 3으로 나누어 1이 남는 수라고 하면 n에서 (n보다 작은) 10^k 를 빼면 3의 배수가 된다. 10^k는 3으로 나누어 1이 남는 수이므로 n = (n - 10^k) + 10^k 는 3으로 나누어 1이 남는다. 같은 방법으로 각 자리수의 합이 3으로 나누어 2가 남는다는 것과 이 수를 3으로 나누었을 때 2가 남게 된다는 것은 동치라는 것을 보일 수 있다.)

아무튼.. 600^5 / 120 도 너무 커서 계산 불가! 다른 방법을 찾아야 한다.

일단 두개씩 비교하는 건 600^2 정도에 가능하니까..
chains라는 dictionary에 i번째 소수와 짝이 될 수 있는(두 개를 붙였을 때 소수가 되는) 소수(의 인덱스)를 저장해 둔다
0:{2,5,7,8,10}
1:{2,5,8,11}
2:{5,7,8,10}
...

그리고 chains안에 있는 0, 1, 2.. loop을 돌면서
{2,5,7,8,10} 에서 4개짜리 세트를 골라내고, (예를 들어, (2,5,8,10)이 뽑혔다면)
{5,8,10}이 chains[2]에 포함되는지 체크한다.
포함된다면, {8,10}이 chains[5]에 포함되는지, 10이 chains[8]에 포함되는지 체크한다.
여기까지 조건을 만족하면 합을 출력한다.

def rwh_primes1(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * (n/2)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

def chk_pn(n,pn):
    for p in pn:
        if n % p == 0: return False
        if p ** 2 > n: return True

def choose4(lst):
    l = len(lst)
    out = []
    for i in range(l):
        for j in range(i+1,l):
            for k in range(j+1,l):
                for w in range(k+1,l):
                    out.append((lst[i],lst[j],lst[k],lst[w]))
    return out

def prob60(pnt,pn):
    l, chains = len(pnt), {}
    for i in range(l):
        for j in range(i+1,l):
            if chk_pn(int(`pnt[i]`+`pnt[j]`),pn) and chk_pn(int(`pnt[j]`+`pnt[i]`),pn):
                if i in chains: chains[i].add(j)
                else: chains[i] = {j}
    
    for i in chains:
        if len(chains[i]) >= 4:
            for comb in choose4(sorted(list(chains[i]))):
                a,b,c,d = comb
                try:
                    if {b,c,d} <= chains[a] and {c,d} <= chains[b] and d in chains[c]:
                        print pnt[i]+pnt[a]+pnt[b]+pnt[c]+pnt[d]
                except:
                    pass
    

pn = rwh_primes1(10000)
pn1 = [3]+[x for x in pn if x%3==1]
pn2 = [3]+[x for x in pn if x%3==2]

prob60(pn1,pn)
prob60(pn2,pn)

40초..
13 + 5197 + 5701 + 6733 + 8389 = 26033
여러개 나왔으면 그 중 가장 작은 것을 고를텐데, 만 이하 소수들로는 한 세트 밖에 못 만든다.
lowest sum을 찾는 문제니까 (작은수)+(작은수)+(작은수)+(작은수)+(만을 약간 넘는 수) 같은 경우가 답이 될 수도 있다.
2만5천 이하의 소수로 확장해서 다시 돌려보면 될텐데.. 오래 걸리는 걸 돌리기는 귀찮다.