[Project Euler] 46. Goldbach's other conjecture

1. 개요

  문제는 이곳에서 확인할 수 있다. odd composite number는 소수가 아닌 홀수인데, 골든바흐는 odd composite number를 아래와 같이 어떤 소수 $p$와 어떤 수 $k$의 제곱의 두배의 합으로 표현할 수 있을 것이라고 추측하였다. 

$9=7+2\times 1^2$

$15=7+2\times 2^2$

$21=3+2\times 3^2$

$25=7+2\times 3^2$

$27=19+2\times 2^2$

$33=31+2\times 1^2$

  하지만 이 추측은 틀렸다. 이 추측에 맞지 않는 가장 작은 odd composite number를 찾는 것이 문제의 목표이다. 

2. 구현

  앞선 문제와 마찬가지로 에라스토테네스의 체를 사용하여 소수를 구한다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

# -*- coding: utf-8 -*-   class Prime:           def __init__(self):         init_max_int = 2         self.is_prime = bytearray([1]) * (init_max_int+1)         self.is_prime[0] = self.is_prime[1] = 0         self.make_more_prime()               def make_more_prime(self):         self.is_prime += bytearray([1])*(len(self.is_prime)+1)         max_int = len(self.is_prime)-1                   for i in range(2, int(max_int**1/2)+1):             if self.is_prime[i]:                 m = max_int//i - i + 1                 self.is_prime[i**2::i] = bytearray([0])*m   p = Prime() n = 9 # first odd composite number   while True:               while len(p.is_prime) <= n:         p.make_more_prime()           if not p.is_prime[n] and not n % 2 == 0:                   for idx in range(n-2, 0, -2):             k = ((n - idx)/2)**0.5                           if p.is_prime[idx] and k % 1 == 0:                 print('{n} = {prime} + 2*{k}^2'.format(n=n, prime=idx, k=int(k)))                 break         else:             print('ANSWER: {answer}'.format(answer=n))             quit()     n += 2

답은 5777이다.