본문 바로가기

오일러프로젝트

[오일러프로젝트] 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

이 추측은 잘못되었음이 밝혀졌습니다.

위와 같은 방법으로 나타낼 수 없는 가장 작은 홀수 합성수는 얼마입니까?



일단 

x=a+2*n^2으로 식을 나타내면

x는 홀수인 합성수, a는 소수, n은 sqrt(x)보다 작은 수여야 한다는 것을 알 수 있다.

x=5부터 loop를 돌리되 x까지의 소수 리스트를 먼저 구한 후

sqrt(x)로부터 n의 범위를 정한다음 위 식을 만족하는 수가 하나도 없는 것을 찾아냄



Python
Ruby
Perl