Problemas
1640년 12월 25일, 위대한 수학자 페르마는 메르센에게 홀수 소수인 p에 대해서 p = 4c + 1 꼴로 표현이 가능할 때
p = a2 + b2 꼴로 표현이 가능하다는 것을 증명했다고 편지를 썼다.(a , b , c : 정수)
여느 때와 같이, 페르마는 우리가 알고 있는 것처럼 증명을 적지 않았다.
이는 100년 뒤에서야 오일러가 이를 증명하였다.
예를 들자면, 아래와 같이 주어진 소수들은 2개의 제곱의 합으로 표현이 가능하다.
5 = 22+ 12 13 = 32 + 22 17 = 42 + 12 41 = 52 + 42
소수 11, 19, 23, 31은 2개의 제곱의 합으로 표현되지 못한다 (4c + 1 꼴의 소수가 아니기에)
주어진 구간에서 두 개의 제곱의 합으로 표현될 수 있는 소수의 개수를 세는 프로그램을 작성하라.
Entrada
당신의 프로그램은 한 개 또는 그 이상의 테스트 케이스에 의해서 점검된다.
각각의 테스트 케이스는 2개의 정수 L, U(L ≤ U < 1,000,000)로 구성된다.
Salida
각 테스트케이스에 대해서, 아래와 같은 형식으로 결과를 출력하라 :
L U x y
L, U는 입력에서 주어진 수이고, x는 [L, U] 구간안에 있는 소수의 총 개수를 말하고 y는 이 구간 안에 있는 두개의 제곱의 합으로 표현이 가능한 소수의 총 개수를 말한다.
Ejemplo
10 20
11 19
100 1000
-1 -1
10 20 4 2
11 19 4 2
100 1000 143 69
Pista
Debes iniciar sesión para escribir código.