시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 435 321 275 77.031%

문제

연속한 소수 p와 p+n이 있을 때, 그 사이에 있는 n-1개의 합성수(소수나 1이 아닌 양의 정수)는 길이가 n인 소수 사이 수열라고 부른다.

양의 정수 k가 주어졌을 때, k를 포함하는 소수 사이 수열의 길이를 구하는 프로그램을 작성하시오. k를 포함하는 소수 사이 수열이 없을 때는 길이가 0이다.

예를 들어, 소수 23과 29의 소수 사이 수열은 {24, 25, 26, 27, 28}이고, 길이는 6이다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 테스트 케이스는 한 줄로 이루어져 있고, 한 줄에 정수 k가 주어진다. 각각의 정수는 1보다 크고, 100000번째 소수(1299709)와 작거나 같다.

출력

각각의 테스트 케이스에 대해서 k가 합성수라면 k를 포함하는 소수 사이 수열의 길이를 출력한다. 그렇지 않으면 0을 출력한다.

예제 입력 1

5
10
11
27
2
492170

예제 출력 1

4
0
6
0
114
W3sicHJvYmxlbV9pZCI6IjM4OTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWMyMTggXHVjMGFjXHVjNzc0IFx1YzIxOFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNWYwXHVjMThkXHVkNTVjIFx1YzE4Y1x1YzIxOCBwXHVjNjQwIHArblx1Yzc3NCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWFkZjggXHVjMGFjXHVjNzc0XHVjNWQwIFx1Yzc4OFx1YjI5NCBuLTFcdWFjMWNcdWM3NTggXHVkNTY5XHVjMTMxXHVjMjE4KFx1YzE4Y1x1YzIxOFx1YjA5OCAxXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4KVx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgblx1Yzc3OCBcdWMxOGNcdWMyMTggXHVjMGFjXHVjNzc0IFx1YzIxOFx1YzVmNFx1Yjc3Y1x1YWNlMCBcdWJkODBcdWI5NzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTgga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBrXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWMxOGNcdWMyMTggXHVjMGFjXHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIGtcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHViMjk0IFx1YzE4Y1x1YzIxOCBcdWMwYWNcdWM3NzQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzVjNlx1Yzc0NCBcdWI1NGNcdWIyOTQgXHVhZTM4XHVjNzc0XHVhYzAwIDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzE4Y1x1YzIxOCAyM1x1YWNmYyAyOVx1Yzc1OCBcdWMxOGNcdWMyMTggXHVjMGFjXHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc0MCB7MjQsIDI1LCAyNiwgMjcsIDI4fVx1Yzc3NFx1YWNlMCwgXHVhZTM4XHVjNzc0XHViMjk0IDZcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTgga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM4MTVcdWMyMThcdWIyOTQgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjZTAsIDEwMDAwMFx1YmM4OFx1YzlmOCBcdWMxOGNcdWMyMTgoMTI5OTcwOSlcdWM2NDAgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMga1x1YWMwMCBcdWQ1NjlcdWMxMzFcdWMyMThcdWI3N2NcdWJhNzQga1x1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWIyOTQgXHVjMThjXHVjMjE4IFx1YzBhY1x1Yzc3NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzODk2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUHJpbWUgR2FwIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgc2VxdWVuY2Ugb2YgbiZtaW51czsxIGNvbnNlY3V0aXZlIGNvbXBvc2l0ZSBudW1iZXJzIChwb3NpdGl2ZSBpbnRlZ2VycyB0aGF0IGFyZSBub3QgcHJpbWUgYW5kIG5vdCBlcXVhbCB0byAxKSBseWluZyBiZXR3ZWVuIHR3byBzdWNjZXNzaXZlIHByaW1lIG51bWJlcnMgcCBhbmQgcCArIG4gaXMgY2FsbGVkIGEgcHJpbWUgZ2FwIG9mIGxlbmd0aCBuLiBGb3IgZXhhbXBsZSwgJmx0OzI0LDI1LDI2LDI3LDI4Jmd0OyBiZXR3ZWVuIDIzIGFuZCAyOSBpcyBhIHByaW1lIGdhcCBvZiBsZW5ndGggNi48XC9wPlxyXG5cclxuPHA+WW91ciBtaXNzaW9uIGlzIHRvIHdyaXRlIGEgcHJvZ3JhbSB0byBjYWxjdWxhdGUsIGZvciBhIGdpdmVuIHBvc2l0aXZlIGludGVnZXIgaywgdGhlIGxlbmd0aCBvZiB0aGUgcHJpbWUgZ2FwIHRoYXQgY29udGFpbnMgay4gRm9yIGNvbnZlbmllbmNlLCB0aGUgbGVuZ3RoIGlzIGNvbnNpZGVyZWQgMCBpbiBjYXNlIG5vIHByaW1lIGdhcCBjb250YWlucyBrLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGlzIGEgc2VxdWVuY2Ugb2YgbGluZXMgZWFjaCBvZiB3aGljaCBjb250YWlucyBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyLiBFYWNoIHBvc2l0aXZlIGludGVnZXIgaXMgZ3JlYXRlciB0aGFuIDEgYW5kIGxlc3MgdGhhbiBvciBlcXVhbHRvIHRoZSAxMDAwMDB0aCBwcmltZSBudW1iZXIsIHdoaWNoIGlzIDEyOTk3MDkuIFRoZSBlbmQgb2YgdGhlIGlucHV0IGlzIGluZGljYXRlZCBieSBhIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSB6ZXJvLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgc2hvdWxkIGJlIGNvbXBvc2VkIG9mIGxpbmVzIGVhY2ggb2Ygd2hpY2ggY29udGFpbnMgYSBzaW5nbGUgbm9uLW5lZ2F0aXZlIGludGVnZXIuIEl0IGlzIHRoZSBsZW5ndGggb2YgdGhlIHByaW1lIGdhcCB0aGF0IGNvbnRhaW5zIHRoZSBjb3JyZXNwb25kaW5nIHBvc2l0aXZlIGludGVnZXIgaW4gdGhlIGlucHV0IGlmIGl0IGlzIGEgY29tcG9zaXRlIG51bWJlciwgb3IgMCBvdGhlcndpc2UuIE5vIG90aGVyIGNoYXJhY3RlcnMgc2hvdWxkIG9jY3VyIGluIHRoZSBvdXRwdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Asia > Japan > Asia Regional Contest 2007 in Tokyo B번

  • 문제를 번역한 사람: baekjoon
  • 잘못된 조건을 찾은 사람: csh519
  • 잘못된 번역을 찾은 사람: jh05013