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