[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. 구현

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

# -*- 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이다.