프로젝트 오일러 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

소수확인 함수는 앞선 문제들에서는 만들어 사용하기도 했는데(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)

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 법이라 느리긴 한데, 답이 나오긴 하는군요. 좀더 좋은 방법이 생각나면 또 업데이트 하도록 하겠습니다.

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

Quadratic primes

예제코드 구현

Solution (Brute Force 방법)

댓글