4798번 - 등차수열에 관한 디리클레의 정리 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB32142179.043%

문제

등차수열에 관한 디리클레의 정리는 서로소인 두 양의 정수 a와 b가 있을 때, 등차수열 t(n) = a*n + b (n ≥ 0)은 무한히 많은 소수를 포함한다는 내용이다. 소수는 2보다 큰 양의 정수로, 약수가 1과 자기자신 밖에 없는 수이다.

예를 들어, a=4, b=3인 경우 등차수열은 다음과 같다.

3, 7, 11, 15, 19, 23, 27, 31, 35, ...,

여기서 이 등차수열의 첫 부분에 많은 소수가 있음을 눈으로 볼 수 있다.

a > 0과 b ≥ 0, 그리고 U ≥ L ≥ 0이 주어졌을 때, t(n) = a*n+b에 소수가 몇 개 있는지 구하는 프로그램을 작성하시오. (L ≤ n ≤ U)

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 a, b, L, U를 포함하며, 한 줄로 이루어져 있다. a*U+b ≤ 1012이고, U - L ≤ 106이다. 마지막 줄에는 0이 주어진다.

출력

각 테스트 케이스에 대해서, 테스트 케이스 번호와 L ≤ n ≤ U에서 t(n)이 소수인 것의 개수를 출력한다.

예제 입력 1 

4 3 0 8
1 0 2 100
2 7 0 1000
0

예제 출력 1 

Case 1: 6
Case 2: 25
Case 3: 301
W3sicHJvYmxlbV9pZCI6IjQ3OTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI0ZjFcdWNjMjhcdWMyMThcdWM1ZjRcdWM1ZDAgXHVhZDAwXHVkNTVjIFx1YjUxNFx1YjlhY1x1ZDA3NFx1YjgwOFx1Yzc1OCBcdWM4MTVcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjRmMVx1Y2MyOFx1YzIxOFx1YzVmNFx1YzVkMCBcdWFkMDBcdWQ1NWMgXHViNTE0XHViOWFjXHVkMDc0XHViODA4XHVjNzU4IFx1YzgxNVx1YjlhY1x1YjI5NCBcdWMxMWNcdWI4NWNcdWMxOGNcdWM3NzggXHViNDUwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggYVx1YzY0MCBiXHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1YjRmMVx1Y2MyOFx1YzIxOFx1YzVmNCB0KG4pID0gYSpuICsgYiAobiAmZ2U7IDApXHVjNzQwIFx1YmIzNFx1ZDU1Y1x1ZDc4OCBcdWI5Y2VcdWM3NDAgXHVjMThjXHVjMjE4XHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1Y1x1YjJlNFx1YjI5NCBcdWIwYjRcdWM2YTlcdWM3NzRcdWIyZTQuIFx1YzE4Y1x1YzIxOFx1YjI5NCAyXHViY2Y0XHViMmU0IFx1ZDA3MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViODVjLCBcdWM1N2RcdWMyMThcdWFjMDAgMVx1YWNmYyBcdWM3OTBcdWFlMzBcdWM3OTBcdWMyZTAgXHViYzE2XHVjNWQwIFx1YzVjNlx1YjI5NCBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIGE9NCwgYj0zXHVjNzc4IFx1YWNiZFx1YzZiMCBcdWI0ZjFcdWNjMjhcdWMyMThcdWM1ZjRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+MywgNywgMTEsIDE1LCAxOSwgMjMsIDI3LCAzMSwgMzUsIC4uLiw8XC9wPlxyXG5cclxuPHA+XHVjNWVjXHVhZTMwXHVjMTFjIFx1Yzc3NCBcdWI0ZjFcdWNjMjhcdWMyMThcdWM1ZjRcdWM3NTggXHVjY2FiIFx1YmQ4MFx1YmQ4NFx1YzVkMCBcdWI5Y2VcdWM3NDAgXHVjMThjXHVjMjE4XHVhYzAwIFx1Yzc4OFx1Yzc0Y1x1Yzc0NCBcdWIyMDhcdWM3M2NcdWI4NWMgXHViY2ZjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmEgJmd0OyAwXHVhY2ZjIGIgJmdlOyAwLCBcdWFkZjhcdWI5YWNcdWFjZTAgVSAmZ2U7IEwgJmdlOyAwXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIHQobikgPSBhKm4rYlx1YzVkMCBcdWMxOGNcdWMyMThcdWFjMDAgXHViYTg3IFx1YWMxYyBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIChMICZsZTsgbiAmbGU7IFUpPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IGEsIGIsIEwsIFVcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHViYTcwLCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIGEqVStiICZsZTsgMTA8c3VwPjEyPFwvc3VwPlx1Yzc3NFx1YWNlMCwgVSAtIEwgJmxlOyAxMDxzdXA+NjxcL3N1cD5cdWM3NzRcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOFx1YzY0MCBMICZsZTsgbiAmbGU7IFVcdWM1ZDBcdWMxMWMgdChuKVx1Yzc3NCBcdWMxOGNcdWMyMThcdWM3NzggXHVhYzgzXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNDc5OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRpcmljaGxldCdzIFRoZW9yZW0iLCJkZXNjcmlwdGlvbiI6IjxwPkRpcmljaGxldCYjMzk7cyB0aGVvcmVtIG9uIGFyaXRobWV0aWMgcHJvZ3Jlc3Npb25zIHN0YXRlcyB0aGF0IGZvciBhbnkgdHdvIHBvc2l0aXZlIGludGVnZXJzIGEgYW5kIGIsIGlmIGdjZChhLGIpID0gMSB0aGVuIHRoZSBhcml0aG1ldGljIHByb2dyZXNzaW9uIHQobikgPSBhKm4gKyBiIChuICZnZTsgMCkgY29udGFpbnMgaW5maW5pdGVseSBtYW55IHByaW1lIG51bWJlcnMuIFJlY2FsbCB0aGF0IGEgcHJpbWUgbnVtYmVyIGlzIGEgcG9zaXRpdmUgaW50ZWdlciAmZ2U7IDIgdGhhdCBoYXMgbm8gZGl2aXNvcnMgb3RoZXIgdGhhbiAxIGFuZCBpdHNlbGYuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBpZiBhID0gNCBhbmQgYiA9IDMsIHRoZW4gdGhlIGFyaXRobWV0aWMgcHJvZ3Jlc3Npb24gaXM8XC9wPlxyXG5cclxuPHA+MywgNywgMTEsIDE1LCAxOSwgMjMsIDI3LCAzMSwgMzUsIC4uLiw8XC9wPlxyXG5cclxuPHA+YW5kIGl0IGNhbiBiZSBzZWVuIHRoYXQgbWFueSBwcmltZSBudW1iZXJzIGFyZSBjb250YWluZWQgaW4gdGhlIGZpcnN0IHBhcnQgb2YgdGhpcyBsaXN0LjxcL3A+XHJcblxyXG48cD5HaXZlbiBhcmJpdHJhcnkgaW50ZWdlcnMgYSAmZ3Q7IDAsIGIgJmdlOyAwLCBhbmQgVSAmZ2U7IEwgJmdlOyAwLCB5b3VyIGpvYiBpcyB0byBjb3VudCBob3cgbWFueSB2YWx1ZXMgb2YgdChuKSA9IGEqbitiIGFyZSBwcmltZSwgd2hlcmUgTCAmbGU7IG4gJmxlOyBVLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIGEgbnVtYmVyIG9mIGNhc2VzLiBUaGUgaW5wdXQgZm9yIGVhY2ggY2FzZSBpcyBzcGVjaVx1ZmIwMWVkIGJ5IHRoZSBmb3VyIGludGVnZXJzIGEsIGIsIEwsIGFuZCBVIG9uIGEgbGluZS4gWW91IG1heSBhc3N1bWUgdGhhdCBhKlUrYiAmbGU7IDEwPHN1cD4xMjxcL3N1cD4gYW5kIFUgLSBMICZsZTsgMTA8c3VwPjY8XC9zdXA+LiBBIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSAwIGluZGljYXRlcyB0aGUgZW5kIG9mIGlucHV0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQ6PFwvcD5cclxuXHJcbjxwPkNhc2UgeHh4OiB5eXk8XC9wPlxyXG5cclxuPHA+d2hlcmUgeHh4IGlzIHRoZSBjYXNlIG51bWJlciAoc3RhcnRpbmcgZnJvbSAxKSwgYW5kIHl5eSBpcyB0aGUgbnVtYmVyIG9mIHQobiksIEwgJmxlOyBuICZsZTsgVSwgdGhhdCBhcmUgcHJpbWUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > North America > Rocky Mountain Regional > 2012 Rocky Mountain Regional Contest C번

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)