시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 2220 | 376 | 270 | 17.330% |
1640년 12월 25일, 위대한 수학자 피에르 드 페르마는 마랭 메르센에게 다음과 같은 내용의 편지를 썼다.
I just proved that an odd prime p is expressible as p = a2 + b2 if and only if p is expressible as p = 4c + 1.
편지에는 증명은 포함되어 있지 않았고, 100년후에 오일러가 증명했다. 5, 13, 17, 41은 두 제곱수의 합으로 나타낼 수 있다.
5=22+11 13=32+22 17=42+12 41=52+42
하지만, 11, 19, 23, 31은 제곱수의 합으로 나타낼 수 없다.
어떤 구간이 주어졌을 때, 이 구간에 포함되어 있는 소수를 제곱수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L과 U가 공백으로 구분되어 주어진다. (-1,000,000 < L ≤ U < 1,000,000)
입력의 마지막 줄은 L과 U가 -1이다.
각 테스트 케이스에 대해서, 한 줄에 L U x y를 출력한다. 여기서 L과 U는 입력으로 주어진 값이고, x는 구간 [L,U]에 포함된 소수의 개수, y는 [L,U]에 포함된 소수중 제곱수의 합으로 나타낼 수 있는 것의 개수이다.
10 20 11 19 100 1000 -1 -1
10 20 4 2 11 19 4 2 100 1000 143 69
ICPC > Regionals > Africa and Arab > Arab Collegiate Programming Contest > 2007 Arab Collegiate Programming Contest E번