Project Euler #27 - quadratic primes

프로젝트 오일러 27번

n^2 + a*n + b 에서 a, b를 잘 찾으면 n = 0,1,2,3,... 을 넣어서 꽤 많은 소수를 찾을 수 있다. |a|, |b| < 1000 조건에서 n이 어디까지 커질 수 있는가?

b 에 대해

1. 문제에서 든 예시에 a=1, b = 41 일 때 n = 0,1,2,...39 까지 모두 소수라는 게 있으니 baseline은 "40"

1.1. b = 23*37 이라고 해 보자, 그럼 n = 23일 때 소수가 될 수 없다. baseline이 40이라면.. b는 소수이거나, 40보다 큰 소수들의 곱이어야 한다. 그런데 41*41만 하더라도 1000을 넘어가 버리니까... b는 41 이상의 소수이어야 한다.

2. 문제에서 든 예시에 a=-79, b = 1601 일 때 n = 0,1,2,...,79 까지 모두 소수라는 게 있으니 아마 |b| < 1000 조건에서는 그보다 작지 않을까 추측해 볼 수 있다. 일단 넉넉하게 n = 100까지 커질 수 있다고 보고, 그럼 n^2+a*n+b 는 111000이 최대.

a 에 대해

위에서 적은 이유로 b는 홀수, n은 홀짝이 모두 가능

a가 짝수라면.. n에 홀수일 때 n^2 => 홀, a*n => 짝, b => 홀 이 되어 전체가 짝이 되어 버리고 소수가 될 수 없다. 그럼 a는 홀수.

(b 를 3으로 나누었을 때 나머지가 1이 될 수 없다.. 이런 조건도 체크해 볼 수 있을 듯...)

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]]

pns = set(rwh_primes1(120000))
bs = [x for x in rwh_primes1(1000) if x > 40]
bs += [-x for x in bs]

def chkmx(a,b):
    for n in range(100):
        if n*n+n*a+b not in pns: return n
    return 100

mx, ma, mb = 41, 1, 41
for a in range(-999,999,2):
    for b in bs:
        if chkmx(a,b) > mx: 
            mx, ma, mb = chkmx(a,b), a, b

if mx >= 100: print "CHECK AGAIN"
else: print ma*mb

'a'에도 뭔가 조건을 주고 싶은데.. 모르겠다.

0.6초 정도에 답이 나오는 걸로 만족