시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB222037627017.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]에 포함된 소수중 제곱수의 합으로 나타낼 수 있는 것의 개수이다.

예제 입력 1

10 20
11 19
100 1000
-1 -1

예제 출력 1

10 20 4 2
11 19 4 2
100 1000 143 69
W3sicHJvYmxlbV9pZCI6IjQ5MTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzOThcdWI5NzRcdWI5YzhcdWM3NTggXHVkMDZjXHViOWFjXHVjMmE0XHViOWM4XHVjMmE0IFx1YzgxNVx1YjlhYyIsImRlc2NyaXB0aW9uIjoiPHA+MTY0MFx1YjE0NCAxMlx1YzZkNCAyNVx1Yzc3YywgXHVjNzA0XHViMzAwXHVkNTVjIFx1YzIxOFx1ZDU1OVx1Yzc5MCBcdWQ1M2NcdWM1ZDBcdWI5NzQgXHViNGRjIFx1ZDM5OFx1Yjk3NFx1YjljOFx1YjI5NCBcdWI5YzhcdWI3YWQgXHViYTU0XHViOTc0XHVjMTNjXHVjNWQwXHVhYzhjIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViMGI0XHVjNmE5XHVjNzU4IFx1ZDNiOFx1YzljMFx1Yjk3YyBcdWMzN2NcdWIyZTQuPFwvcD5cclxuXHJcbjxibG9ja3F1b3RlPkkganVzdCBwcm92ZWQgdGhhdCBhbiBvZGQgcHJpbWUgcCBpcyBleHByZXNzaWJsZSBhcyBwID0gYTxzdXA+MjxcL3N1cD4gKyBiPHN1cD4yPFwvc3VwPiBpZiBhbmQgb25seSBpZiBwIGlzIGV4cHJlc3NpYmxlIGFzIHAgPSA0YyArIDEuPFwvYmxvY2txdW90ZT5cclxuXHJcbjxwPlx1ZDNiOFx1YzljMFx1YzVkMFx1YjI5NCBcdWM5OWRcdWJhODVcdWM3NDAgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM1NThcdWFjZTAsIDEwMFx1YjE0NFx1ZDZjNFx1YzVkMCBcdWM2MjRcdWM3N2NcdWI3ZWNcdWFjMDAgXHVjOTlkXHViYTg1XHVkNTg4XHViMmU0LiA1LCAxMywgMTcsIDQxXHVjNzQwIFx1YjQ1MCBcdWM4MWNcdWFjZjFcdWMyMThcdWM3NTggXHVkNTY5XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD41PTI8c3VwPjI8XC9zdXA+KzE8c3VwPjE8XC9zdXA+IDEzPTM8c3VwPjI8XC9zdXA+KzI8c3VwPjI8XC9zdXA+IDE3PTQ8c3VwPjI8XC9zdXA+KzE8c3VwPjI8XC9zdXA+IDQxPTU8c3VwPjI8XC9zdXA+KzQ8c3VwPjI8XC9zdXA+PFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYywgMTEsIDE5LCAyMywgMzFcdWM3NDAgXHVjODFjXHVhY2YxXHVjMjE4XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1YWQ2Y1x1YWMwNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHVhZDZjXHVhYzA0XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjMThjXHVjMjE4XHViOTdjIFx1YzgxY1x1YWNmMVx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBMXHVhY2ZjIFVcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgtMSwwMDAsMDAwICZsdDsgTCAmbGU7IFUgJmx0OyAxLDAwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNzQwIExcdWFjZmMgVVx1YWMwMCAtMVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgTCBVIHggeVx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzVlY1x1YWUzMFx1YzExYyBMXHVhY2ZjIFVcdWIyOTQgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWFjMTJcdWM3NzRcdWFjZTAsIHhcdWIyOTQgXHVhZDZjXHVhYzA0IFtMLFVdXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxYyBcdWMxOGNcdWMyMThcdWM3NTggXHVhYzFjXHVjMjE4LCB5XHViMjk0IFtMLFVdXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxYyZuYnNwO1x1YzE4Y1x1YzIxOFx1YzkxMSBcdWM4MWNcdWFjZjFcdWMyMThcdWM3NTggXHVkNTY5XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNDkxMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZlcm1hdFx1MjAxOXMgQ2hpcnN0bWFzIFRoZW9yZW0iLCJkZXNjcmlwdGlvbiI6IjxwPkluIGEgbGV0dGVyIGRhdGVkIERlY2VtYmVyIDI1LCAxNjQwOyB0aGUgZ3JlYXQgbWF0aGVtYXRpY2lhbiBQaWVycmUgZGUgRmVybWF0IHdyb3RlIHRvIE1hcmluIE1lcnNlbm5lIHRoYXQgaGUganVzdCBwcm92ZWQgdGhhdCBhbiBvZGQgcHJpbWUgcCBpcyBleHByZXNzaWJsZSBhcyBwID0gYTxzdXA+MjxcL3N1cD4gKyBiPHN1cD4yPFwvc3VwPiBpZiBhbmQgb25seSBpZiBwIGlzIGV4cHJlc3NpYmxlIGFzIHAgPSA0YysxLiBBcyB1c3VhbCwgRmVybWF0IGRpZG5cdTAwOTB0IGluY2x1ZGUgdGhlIHByb29mLCBhbmQgYXMgZmFyIGFzIHdlIGtub3csIG5ldmVyIHdyb3RlIGl0IGRvd24uIEl0IHdhc25cdTAwOTB0IHVudGlsIDEwMCB5ZWFycyBsYXRlciB0aGF0IG5vIG9uZSBvdGhlciB0aGFuIEV1bGVyIHByb3ZlZCB0aGlzIHRoZW9yZW0uIFRvIGlsbHVzdHJhdGUsIGVhY2ggb2YgdGhlIGZvbGxvd2luZyBwcmltZXMgY2FuIGJlIGV4cHJlc3NlZCBhcyB0aGUgc3VtIG9mIHR3byBzcXVhcmVzOjxcL3A+XHJcblxyXG48cD41PTI8c3VwPjI8XC9zdXA+KzE8c3VwPjE8XC9zdXA+Jm5ic3A7MTM9MzxzdXA+MjxcL3N1cD4rMjxzdXA+MjxcL3N1cD4mbmJzcDsxNz00PHN1cD4yPFwvc3VwPisxPHN1cD4yPFwvc3VwPiZuYnNwOzQxPTU8c3VwPjI8XC9zdXA+KzQ8c3VwPjI8XC9zdXA+PFwvcD5cclxuXHJcbjxwPldoZXJlYXMgdGhlIHByaW1lcyAxMSwgMTksIDIzLCBhbmQgMzEgY2Fubm90IGJlIGV4cHJlc3NlZCBhcyBhIHN1bSBvZiB0d28gc3F1YXJlcy4gV3JpdGUgYSBwcm9ncmFtIHRvIGNvdW50IHRoZSBudW1iZXIgb2YgcHJpbWVzIHRoYXQgY2FuIGJlIGV4cHJlc3NlZCBhcyBzdW0gb2Ygc3F1YXJlcyB3aXRoaW4gYSBnaXZlbiBpbnRlcnZhbC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSB3aWxsIGJlIHRlc3RlZCBvbiBvbmUgb3IgbW9yZSB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBpcyBzcGVjaWZpZWQgb24gYSBzZXBhcmF0ZSBpbnB1dCBsaW5lIHRoYXQgc3BlY2lmaWVzIHR3byBpbnRlZ2VycyBMLCBVIHdoZXJlIC0xLDAwMCwwMDAgJmx0OyBMICZsZTsgVSAmbHQ7IDEsMDAwLDAwMDxcL3A+XHJcblxyXG48cD5UaGUgbGFzdCBsaW5lIG9mIHRoZSBpbnB1dCBmaWxlIGluY2x1ZGVzIGEgZHVtbXkgdGVzdCBjYXNlIHdpdGggYm90aCBMID0gVSA9ICZtaW51czsxLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgd3JpdGUgdGhlIHJlc3VsdCB1c2luZyB0aGUgZm9sbG93aW5nIGZvcm1hdDo8XC9wPlxyXG5cclxuPHByZT5cclxuTFx1MDAwMiBVIFx1MDAwMnhcdTAwMDIgeTxcL3ByZT5cclxuXHJcbjxwPndoZXJlIEwgYW5kIFUgYXJlIGFzIHNwZWNpXHUwMDkzZWQgaW4gdGhlIGlucHV0LiB4IGlzIHRoZSB0b3RhbCBudW1iZXIgb2YgcHJpbWVzIHdpdGhpbiB0aGUgaW50ZXJ2YWwgW0wsIFVdIChpbmNsdXNpdmUsKSBhbmQgeSBpcyB0aGUgdG90YWwgbnVtYmVyIG9mIHByaW1lcyAoYWxzbyB3aXRoaW4gW0wsIFVdKSB0aGF0IGNhbiBiZSBleHByZXNzZWQgYXMgYSBzdW0gb2Ygc3F1YXJlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Africa and Arab > Arab Collegiate Programming Contest > 2007 Arab Collegiate Programming Contest E번