1462: 연속 소수의 합
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 83 Solved: 26
[Submit] [Status] [Web Board] [Creator:]
Description
아래 그림과 같이 소수(prime number) 열이 있다고 할 때 연속한 5개 소수의 합이 다시 소수가 되는지를 판단하는 프로그램을 작성하려고 한다.
예를 들어 위의 그림에서 보면 연속된 5개 소수의 합인 19+23+29+31+37은 139가 되고 139는 소수이다. 마찬가지로 29+31+37+41+43은 181이 되고 이 또한 소수이다.
이처럼 구간이 주어질 경우 그 구간 안(구간의 시작값과 마지막값 포함)에 존재하는 연속된 5개의 소수의 합이 다시 소수가 되는 경우를 모두 찾아 출력하는 프로그램을 작성해 보자.
예를 들어 위의 그림에서 보면 연속된 5개 소수의 합인 19+23+29+31+37은 139가 되고 139는 소수이다. 마찬가지로 29+31+37+41+43은 181이 되고 이 또한 소수이다.
이처럼 구간이 주어질 경우 그 구간 안(구간의 시작값과 마지막값 포함)에 존재하는 연속된 5개의 소수의 합이 다시 소수가 되는 경우를 모두 찾아 출력하는 프로그램을 작성해 보자.
Input
구간값의 시작과 끝을 의미하는 a와 b가 한 줄에 정수로 입력된다.(1 <= a <= b <= 300,000)
이 정수 쌍이 여러 테스트케이스로 입력되며 이 값이 모두 0인 경우에는 프로그램을 종료한다.
주어지는 두 값의 사이에는 적어도 5개의 소수가 존재한다.
이 정수 쌍이 여러 테스트케이스로 입력되며 이 값이 모두 0인 경우에는 프로그램을 종료한다.
주어지는 두 값의 사이에는 적어도 5개의 소수가 존재한다.
Output
각 테스트케이스 별로 구간 내에 존재하는 5개의 연속된 소수의 합이 소수가 되는 경우를 찾아 출력 예시와 같은 형식으로 출력한다.
Sample Input Copy
1 20
1000 1200
10000 10500
0 0
Sample Output Copy
#1:5+7+11+13+17:53
#2:7+11+13+17+19:67
#1:1033+1039+1049+1051+1061:5233
#2:1069+1087+1091+1093+1097:5437
#3:1087+1091+1093+1097+1103:5471
#4:1093+1097+1103+1109+1117:5519
#5:1103+1109+1117+1123+1129:5581
#1:10007+10009+10037+10039+10061:50153
#2:10037+10039+10061+10067+10069:50273
#3:10091+10093+10099+10103+10111:50497
#4:10093+10099+10103+10111+10133:50539
#5:10103+10111+10133+10139+10141:50627
#6:10133+10139+10141+10151+10159:50723
#7:10139+10141+10151+10159+10163:50753
#8:10159+10163+10169+10177+10181:50849
#9:10271+10273+10289+10301+10303:51437
#10:10273+10289+10301+10303+10313:51479
#11:10337+10343+10357+10369+10391:51797
#12:10343+10357+10369+10391+10399:51859