1640년 12월 25일, 위대한 수학자 페르마는 메르센에게 홀수 소수인 p에 대해서 p = 4c + 1 꼴로 표현이 가능할 때

p = a² + b² 꼴로 표현이 가능하다는 것을 증명했다고 편지를 썼다.(a , b , c : 정수)

여느 때와 같이, 페르마는 우리가 알고 있는 것처럼 증명을 적지 않았다.

이는 100년 뒤에서야 오일러가 이를 증명하였다.

예를 들자면, 아래와 같이 주어진 소수들은 2개의 제곱의 합으로 표현이 가능하다.

5 = 2²+ 1² 13 = 3² + 2² 17 = 4² + 1² 41 = 5² + 4²

소수 11, 19, 23, 31은 2개의 제곱의 합으로 표현되지 못한다 (4c + 1 꼴의 소수가 아니기에)

주어진 구간에서 두 개의 제곱의 합으로 표현될 수 있는 소수의 개수를 세는 프로그램을 작성하라.

메르센2 timer 1s memory 128MB

메르센2 1s 128MB