콘텐츠로 건너뛰기
Home » 오일러 프로젝트 46

오일러 프로젝트 46

오일러 프로젝트 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에 대해서 위 추측의 반례인지를 확인하는 코드를 작성하는 것은 간단하다.

  1. N은 홀수여야 함
  2. N은 소수가 아니어야 함
  3. N의 절반보다 작은 제곱수의 목록을 만들고
  4. N보다 작은 소수체를 만든다.
  5. N보다 작은 제곱수  S에 대해서 N – S * 2 의 값을 계산하고, 이 값을 소수체에서 검사해서 있으면 추측을 만족, 없으면 반례가 된다.

그런데 매 N을 변경할 때마다 소수체를 만드는 것이 되려 비효율적일 수 있으므로, 다음과 같이 개선했다.

  1. 소수 판별은 소수체를 사용하지 않고 효율적인 소수 검사 함수를 사용한다.
  2. 제곱근의 절반 범위까지의 완전 제곱수들로 체크한다.

파이썬 풀이

이 포스팅을 수정하기 전의 알고리듬으로는 약 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)
}

%d 블로거가 이것을 좋아합니다: