오일러 프로젝트 27 번은 0부터 연속된 자연수(요즘 대수학에서는 0도 자연수에 포함시킨다하던데…)를 넣었을 때 소수를 계속만들 수 있는 이차식에 대한 문제이다. 바로 가장 긴 소수 수열을 만들 수 있는 계수의 조합을 구한다.
오일러는 다음과 같은 멋진 2차식을 제시했습니다.
이 식의 n에다 0부터 39 사이의 숫자를 넣으면, 그 결과는 모두 소수가 됩니다. 하지만 n = 40일 때의 값
은 40×(40 + 1) + 41 이므로 41로 나누어지고, n = 41일 때 역시 412 + 41 + 41 이므로 소수가 아닙니다.
컴퓨터의 발전에 힘입어이라는 엄청난 2차식이 발견되었는데, 이것은 n이 0에서 79 사이일 때 모두 80개의 소수를 만들어냅니다. 이 식의 계수의 곱은 -79 × 1601 = -126479가 됩니다. 아래와 같은 모양의 2차식이 있다고 가정했을 때,
이 0부터 시작하는 연속된 n에 대해 가장 많은 소수를 만들어내는 2차식을 찾아서, 그 계수 a와 b의 곱을 구하세요.
http://euler.synap.co.kr/prob_detail.php?id=27
접근
이차식의 그래프는 포물선의 모양이다. 이 때 x가 0에서 부터 출발해서 증가할 때 -500식의 결과값이 0보다 크게, 소수를 포함하도록 하고 싶다면 포물선이 좌우 대칭인 점을 이용해서, 가능하면 포물선의 꼭지점이 1사분면에 있는 것이 유리하다. 그러면 0~n 까지가 모두 소수를 만든다고 하면 자동적으로 n~2n까지도 소수가 되기 때문이다.
따라서 포물선의 중심이 1사분면에 오기 위해서는 a는 음수, b는 -2a 보다 큰 조건 만족해야 하고 (여기서 다시 b는 1000보다 작거나 같으므로 a의 범위는 (-500…0) 이된다.), 이를 검사하면 계산량을 비약적으로 줄일 수 있다.
def is_prime(n):
if n < 2: return False
if n in (2, 3): return True
if n % 2 is 0 or n % 3 is 0:
return False
if n < 10: return False
k, l = 5, n ** 0.5
while k <= l:
if n % k == 0 or n % (k+2) == 0:
return False
k += 6
return True
def make_eqation(a, b):
return lambda x: x*x + a*x + b
def test(a:int, b:int) -> int:
fx = make_eqation(a, b)
c = 0
while True:
if fx(c):
c += 1
else:
return c
def main():
mc, result = 0, 0
for a in range(-500, 0):
for b in range(-2*a, 1001):
c = test(a, b)
if mc < c:
mc = c
result = a * b
print(result)
%time main()
# Wall time: 530ms
보너스 Swift 풀이
동일한 로직의 Swift 풀이
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import Foundation | |
func timeit(_ f: () -> ()) { | |
let s = Date() | |
f() | |
print("time: \(s.timeIntervalSinceNow * -1000)ms") | |
} | |
func isPrime(_ n: Int) -> Bool { | |
if n < 2 { return false } | |
if (2…3) ~= n { return true } | |
if n % 2 == 0 || n % 3 == 0 { return false } | |
if n < 10 { return true } | |
var k = 5 | |
let l = Int(sqrt(Double(n)) + 0.5) | |
while k <= l { | |
if n % k == 0 || n % (k + 2) == 0 { return false } | |
k += 6 | |
} | |
return true | |
} | |
func test(_ a: Int, _ b: Int) -> Int { | |
let eq: (Int) -> Bool = { n -> Bool in | |
let k = n * n + a * n + b | |
return isPrime(k) | |
} | |
var n = 0 | |
while true { | |
if eq(n) { | |
n += 1 | |
} else { | |
return n | |
} | |
} | |
} | |
func solve() { | |
var m = 0 | |
var result = 0 | |
for a in stride(from: -1, through:-500, by: -1) { | |
for b in ((-2*a)…1000) { | |
let n = test(a, b) | |
if n > m { | |
m = n | |
result = a * b | |
} | |
} | |
} | |
print(result) | |
} | |
timeit(solve) |