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 모듈을 이용하도록 하겠습니다.
예제코드 구현
1 2 3 4 5 6 7 8 | from sympy import isprimefor 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차방정식으로 생성되는 소수는 범위내의 모든 소수가 아님을 알수 있습니다.
1 2 3 4 5 6 7 8 9 | #범위내 모든 소수의 갯수는 240개from sympy import isprimecount =0for i in range(41,1602): if isprime(i): count+=1print(count) |
Solution (Brute Force 방법)
딱히 좋은 방법이 생각이 안나서 일단 Brute Force 방법으로, 2차방정식의 a,b 부분을 루프문으로 변화시켜가며, 모든 값을 한번 조사해 보겠습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | from sympy import isprimemax_n=0for 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 법이라 느리긴 한데, 답이 나오긴 하는군요. 좀더 좋은 방법이 생각나면 또 업데이트 하도록 하겠습니다.
