프로젝트 오일러 27번 - 2차 함수로 소수만들기

n^2 + 40n + 41
위 2차 함수에 1~40 까지 대입하면, 40개의 소수가 생성된다고 합니다.

n^2 - 79n + 1601
이런 함수는 1~80 까지 대입하면, 80개의 소수가 생성된다고 합니다.

n^2 + an + b
문제는 위의 식에서 a,b 절대값이 1000 보다 작을때, 앞의 예제처럼 1부터 시작해서 최대갯수의 소수가 생성되도록 하는 a,b의 값을 찾아서 두수의 곱을 계산하는 문제입니다.

Quadratic primes

https://projecteuler.net/problem=27

소수확인 함수는 앞선 문제들에서는 만들어 사용하기도 했는데(3번문제, 7번문제, 10번문제), 간단하게 sympy 모듈을 이용하도록 하겠습니다.

예제코드 구현

from sympy import isprime

for n in range(40):
    value=pow(n,2)+n+41
    print(value,end=' ')
    if isprime(value):
        print("True")
print(0)

41 True
43 True
47 True
...
...
1447 True
1523 True
1601 True

예제에 내온대로 41~1601까지 40개의 소수가 출력되는걸 볼수 있습니다. 실제로 41~1601사이의 소수의 갯수는 240개로, 해당 2차방정식으로 생성되는 소수는 범위내의 모든 소수가 아님을 알수 있습니다.

#범위내 모든 소수의 갯수는 240개

from sympy import isprime

count =0
for i in range(41,1602):
    if isprime(i):
        count+=1
print(count)

240

Solution (Brute Force 방법)

딱히 좋은 방법이 생각이 안나서 일단 Brute Force 방법으로, 2차방정식의 a,b 부분을 루프문으로 변화시켜가며, 모든 값을 한번 조사해 보겠습니다.

from sympy import isprime

max_n=0
for a in range(-1000,1001):
    for b in range(-1000,1001):
        n=0
        while True:
            value = n**2 + a*n + b
            if value>0 and isprime(value):
                n+=1
            else:
                if n>max_n:
                    max_n = n
                    print("a:",a,"b:",b,"new max value n:",n,a*b)
                    break
                else:
                    break

a: -1000 b: 2 new max value n: 1 -2000
a: -996 b: 997 new max value n: 2 -993012
a: -499 b: 997 new max value n: 3 -497503
a: -325 b: 977 new max value n: 4 -317525
a: -245 b: 977 new max value n: 5 -239365
a: -197 b: 983 new max value n: 6 -193651
a: -163 b: 983 new max value n: 7 -160229
a: -131 b: 941 new max value n: 8 -123271
a: -121 b: 947 new max value n: 9 -114587
a: -105 b: 967 new max value n: 11 -101535
a: -61 b: 971 new max value n: 71 -59231

Brute force 법이라 느리긴 한데, 답이 나오긴 하는군요. 좀더 좋은 방법이 생각나면 또 업데이트 하도록 하겠습니다.