오일러 프로젝트 46 번은 은근히 시간이 많이 걸리는 문제이다. 모든 소수가 아닌 홀수가 소수와 제곱수의 두 배의 합으로 나타낼 수 있다는 추측의 반례를 찾는 것이다.
크리스티안 골드바흐는 모든 홀수인 합성수를 (소수 + 2×제곱수)로 나타낼 수 있다고 주장했습니다.
- 9 = 7 + 2×12
- 15 = 7 + 2×22
- 21 = 3 + 2×32
- 25 = 7 + 2×32
- 27 = 19 + 2×22
- 33 = 31 + 2×12
이 추측은 잘못되었음이 밝혀졌습니다. 위와 같은 방법으로 나타낼 수 없는 가장 작은 홀수 합성수는 얼마입니까?(http://euler.synap.co.kr/prob_detail.php?id=46)
접근
임의의 자연수 N에 대해서 위 추측의 반례인지를 확인하는 코드를 작성하는 것은 간단하다.
- N은 홀수여야 함
- N은 소수가 아니어야 함
- N의 절반보다 작은 제곱수의 목록을 만들고
- N보다 작은 소수체를 만든다.
- N보다 작은 제곱수 S에 대해서 N – S * 2 의 값을 계산하고, 이 값을 소수체에서 검사해서 있으면 추측을 만족, 없으면 반례가 된다.
그런데 매 N을 변경할 때마다 소수체를 만드는 것이 되려 비효율적일 수 있으므로, 다음과 같이 개선했다.
- 소수 판별은 소수체를 사용하지 않고 효율적인 소수 검사 함수를 사용한다.
- 제곱근의 절반 범위까지의 완전 제곱수들로 체크한다.
파이썬 풀이
이 포스팅을 수정하기 전의 알고리듬으로는 약 3~4초대가 걸렸는데, 알고리듬 개선으로 약 .15초 이내의 수행 시간이 소요된다. (물론 이전에 테스트했던 파이썬 버전(3.5?)과 지금 버전의 성능 차이도 어느 정도 있을 수 있다.)
from functools import wraps
def memoize(f):
memo = dict()
@wraps(f)
def wrapped(n):
if n in memo:
return memo[n]
r = f(n)
memo[n] = r
return r
return wrapped
@memoize
def is_prime(n):
if n < 2:
return False
if n < 4:
return True
if n % 2 == 0 or n % 3 == 0:
return False
if n < 10:
return True
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 test(n):
if is_prime(n):
return False
x = 1
while x * 2 + 1 < n:
if is_prime(n - x * x * 2):
return False
x += 1
return True
def solve():
a = 9
while not test(a):
a += 2
print(a)
if __name__ == '__main__':
solve()
다음은 오랜만에 Swift 풀이를 추가해봤다. Swift에서 완전제곱수의 제곱근을 구하려면 Int(floor(sqrt(Double(n)))) 같은 괴상한 방식으로 전환을 해야했었는데, 보다 영어 문장에 가까운 메소드들이 생겨서 옮겨보았다.
정수의 배수 판정도 % 연산자를 써서 체크할 수도 있지만, n.isMultiple(of:x) 표현이 가능하다.
// swift 5.0
import Foundation
func isPrime(_ n: Int) -> Bool {
if n < 2 { return false }
if n < 4 { return true }
if n % 2 == 0 || n % 3 == 0 { return false }
if n < 10 { return true }
let l = Int(Double(n).squareRoot().rounded(.down)) + 1
var k = 5
while k < l {
if n.isMultiple(of:k) || n.isMultiple(of:(k+2)) { return false }
k += 6
}
return true
}
func test(_ n: Int) -> Bool {
guard !isPrime(n) else { return false }
var x = 1
while x * 2 + 1 < n {
if isPrime( n - x * x * 2) { return false }
x += 1
}
return true
}
main: do {
let b = Date()
var a = 9
while !test(a) { a += 2 }
let e = Date().timeIntervalSince(b)
print(a)
print(e * 1000)
}