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

문제

정수 K (1 ≤ K ≤ 100,000)가 주어진다. 이때, K보다 크거나 같은 서로 다른 소수의 곱 중에서 가장 작은 곱을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 20)이 주어진다. 다음 T개 줄에는 K가 한 줄에 하나씩 주어진다.

출력

각각의 K마다 K보다 크거나 같은 서로 다른 두 소수의 곱 중에서 가장 작은 곱을 출력한다.

예제 입력 1

5
1
3
10
300
100000

예제 출력 1

6
6
10
301
100001

힌트

K=1인 경우 답은 6 = 2 × 3이다. 6은 서로 다른 두 소수의 곱 중에서 가장 작은 곱이다. 4 = 2 × 2 이기 때문에, 정답이 되지 않는다.

세 번째 예제 K=10인 경우에 정답은 10 = 2 × 5 이다.

마지막 예제 K=100000인 경우 정답은 100001 = 11 × 9091 이다.

W3sicHJvYmxlbV9pZCI6Ijk3NTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5ZGQgXHVhY2YxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWMyMTggSyAoMSAmbGU7IEsgJmxlOyAxMDAsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgS1x1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMThjXHVjMjE4XHVjNzU4IFx1YWNmMSBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWFjZjFcdWM3NDQgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQgKDEgJmxlOyBUICZsZTsgMjApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIFRcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IEtcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiA8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggS1x1YjljOFx1YjJlNCBLXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWI0NTAgXHVjMThjXHVjMjE4XHVjNzU4IFx1YWNmMSBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWFjZjFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5LPTFcdWM3NzggXHVhY2JkXHVjNmIwIFx1YjJmNVx1Yzc0MCA2ID0gMiAmdGltZXM7IDNcdWM3NzRcdWIyZTQuIDZcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWI0NTAgXHVjMThjXHVjMjE4XHVjNzU4IFx1YWNmMSBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWFjZjFcdWM3NzRcdWIyZTQuIDQgPSAyICZ0aW1lczsgMiBcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM4MTVcdWIyZjVcdWM3NzQgXHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTM4IFx1YmM4OFx1YzlmOCBcdWM2MDhcdWM4MWMgSz0xMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVjODE1XHViMmY1XHVjNzQwIDEwID0gMiAmdGltZXM7IDUgXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5YzhcdWM5YzBcdWI5YzkgXHVjNjA4XHVjODFjIEs9MTAwMDAwXHVjNzc4IFx1YWNiZFx1YzZiMCBcdWM4MTVcdWIyZjVcdWM3NDAgMTAwMDAxID0gMTEgJnRpbWVzOyA5MDkxIFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6Ijk3NTMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNdWx0aXBseWluZyBQYWlycyIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gYW4gaW50ZWdlciBLICgxICZsdDs9IEsgJmx0Oz0gMTAwLDAwMCksIGZpbmQgdGhlIHNtYWxsZXN0IGludGVnZXIgbm8gbGVzcyB0aGFuIEsgd2hpY2ggaXMgYSBwcm9kdWN0IG9mIGV4YWN0bHkgdHdvIGRpZmZlcmVudCBwcmltZSBudW1iZXJzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IHNwZWNpZmllcyBhbiBpbnRlZ2VyIFQgKDEgJmx0Oz0gVCAmbHQ7PSAyMCksIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gVGhlbiBUIGxpbmVzIGZvbGxvdywgZWFjaCBsaW5lIGNvbnRhaW5pbmcgb25lIHRlc3QgY2FzZS4gRWFjaCB0ZXN0IGNhc2Ugc3BlY2lmaWVzIG9uZSBpbnRlZ2VyIEsuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBoYXMgVCBsaW5lcywgZWFjaCBmb3IgZWFjaCB0ZXN0IGNhc2UuIEVhY2ggbGluZSBzaG91bGQgc3BlY2lmeSB0aGUgc21hbGxlc3QgaW50ZWdlciBubyBsZXNzIHRoYW4gSyB3aGljaCBpcyBhIHByb2R1Y3Qgb2YgZXhhY3RseSB0d28gZGlmZmVyZW50IHByaW1lIG51bWJlcnMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoZSBmaXJzdCBleGFtcGxlIHdoZXJlIEs9MSwgdGhlIGFuc3dlciBpcyA2IGJlY2F1c2UgNiA9IDIgeCAzIGFuZCBpdCBpcyB0aGUgc21hbGxlc3QgaW50ZWdlciB3aGljaCBpcyBhIHByb2R1Y3Qgb2YgZXhhY3RseSB0d28gZGlmZmVyZW50IHByaW1lIG51bWJlcnMuIE5vdGUgdGhhdCA0IGlzIG5vdCB0aGUgYW5zd2VyIGJlY2F1c2UgNCA9IDIgeCAyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiB0aGUgdGhpcmQgZXhhbXBsZSB3aGVyZSBLPTEwLCB0aGUgYW5zd2VyIGlzIDEwIGJlY2F1c2UgMTAgaXMgYSBwcm9kdWN0IG9mIDIgYW5kIDUsIGJvdGggb2Ygd2hpY2ggYXJlIHByaW1lIG51bWJlcnMgYW5kIDIgYW5kIDUgYXJlIGRpZmZlcmVudC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gdGhlIGxhc3QgZXhhbXBsZSB3aGVyZSBLPTEwMDAwMCwgdGhlIGFuc3dlciBpcyAxMDAwMDEgYmVjYXVzZSAxMDAwMDEgaXMgYSBwcm9kdWN0IG9mIDExIGFuZCA5MDkxLCBib3RoIG9mIHdoaWNoIGFyZSBwcmltZSBudW1iZXJzIGFuZCAyIGFuZCA1IGFyZSBkaWZmZXJlbnQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Asia Pacific > Thailand > Thailand Central Group-B Programming Contest > Thailand Central Group-B Programming Contest 2013 A번