시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 36 1 1 6.667%

문제

그림의 추측이란, 연속된 합성수의 집합이 있을 때, 각각의 수를 나눌 수 있는 서로 다른 소수를 하나씩 배정할 수 있다는 내용이다.

즉, n+1, n+2, ..., n+k가 모두 합성수일 때, (n+i)를 나눌 수 있는 서로 다른 k개의 소수 pi가 존재한다는 내용이다. (1 ≤ i ≤ k)

예를 들어, 242부터 250까지 합성수는 다음과 같이 소수를 배정할 수 있다.

242 243 244 245 246 247 248 249 250
2 3 61 7 41 13 31 83 5

연속된 합성수의 구간이 주어졌을 때, 각각의 합성수를 나눌 수 있는 서로 다른 소수를 찾는 프로그램을 작성하시오. 소수를 배치할 수 있는 방법이 여러가지라면, 첫번째 소수가 가장 작은 것을 출력한다. 그러한 것이 여러가지라면, 두번째 소수가 작은것, 세번째,... 와 같은 식으로 가장 작은 방법을 출력한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L과 H가 주어진다. (4 ≤ L < H ≤ 1010)

항상 L... H구간의 수는 합성수이다.

마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 소수를 공백으로 구분해서 출력한다.

예제 입력 1

242 250
8 10
0 0

예제 출력 1

2 3 61 7 41 13 31 83 5
2 3 5
W3sicHJvYmxlbV9pZCI6IjQ3MDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkZjhcdWI5YmNcdWM3NTggXHVjZDk0XHVjZTIxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFkZjhcdWI5YmNcdWM3NTggXHVjZDk0XHVjZTIxXHVjNzc0XHViNzgwLCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHVkNTY5XHVjMTMxXHVjMjE4XHVjNzU4IFx1YzlkMVx1ZDU2OVx1Yzc3NCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMjE4XHViOTdjIFx1YjA5OFx1YjIwYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMThjXHVjMjE4XHViOTdjIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWJjMzBcdWM4MTVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWIwYjRcdWM2YTlcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzk4OSwgbisxLCBuKzIsIC4uLiwgbitrXHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWQ1NjlcdWMxMzFcdWMyMThcdWM3N2MgXHViNTRjLCAobitpKVx1Yjk3YyBcdWIwOThcdWIyMGMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IGtcdWFjMWNcdWM3NTggXHVjMThjXHVjMjE4IHBpXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNFx1YjI5NCBcdWIwYjRcdWM2YTlcdWM3NzRcdWIyZTQuICgxICZsZTsgaSAmbGU7IGspPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIDI0Mlx1YmQ4MFx1ZDEzMCAyNTBcdWFlNGNcdWM5YzAgXHVkNTY5XHVjMTMxXHVjMjE4XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjMThjXHVjMjE4XHViOTdjIFx1YmMzMFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6MzYlXCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo0JVwiPjI0MjxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo0JVwiPjI0MzxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo0JVwiPjI0NDxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo0JVwiPjI0NTxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo0JVwiPjI0NjxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo0JVwiPjI0NzxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo0JVwiPjI0ODxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo0JVwiPjI0OTxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo0JVwiPjI1MDxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+NjE8XC90ZD5cclxuXHRcdFx0PHRkPjc8XC90ZD5cclxuXHRcdFx0PHRkPjQxPFwvdGQ+XHJcblx0XHRcdDx0ZD4xMzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzE8XC90ZD5cclxuXHRcdFx0PHRkPjgzPFwvdGQ+XHJcblx0XHRcdDx0ZD41PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5cdWM1ZjBcdWMxOGRcdWI0MWMgXHVkNTY5XHVjMTMxXHVjMjE4XHVjNzU4IFx1YWQ2Y1x1YWMwNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjMDFcdWFjMDFcdWM3NTggXHVkNTY5XHVjMTMxXHVjMjE4XHViOTdjIFx1YjA5OFx1YjIwYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMThjXHVjMjE4XHViOTdjIFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWMxOGNcdWMyMThcdWI5N2MgXHViYzMwXHVjZTU4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0IFx1YzVlY1x1YjdlY1x1YWMwMFx1YzljMFx1Yjc3Y1x1YmE3NCwgXHVjY2FiXHViYzg4XHVjOWY4IFx1YzE4Y1x1YzIxOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWFjODNcdWM3NzQgXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwXHViNzdjXHViYTc0LCBcdWI0NTBcdWJjODhcdWM5ZjggXHVjMThjXHVjMjE4XHVhYzAwIFx1Yzc5MVx1Yzc0MFx1YWM4MywgXHVjMTM4XHViYzg4XHVjOWY4LC4uLiBcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YzJkZFx1YzczY1x1Yjg1YyBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgTFx1YWNmYyBIXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDQgJmxlOyBMICZsdDsgSCAmbGU7IDEwPHN1cD4xMDxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlx1ZDU2ZFx1YzBjMSBMLi4uIEhcdWFkNmNcdWFjMDRcdWM3NTggXHVjMjE4XHViMjk0IFx1ZDU2OVx1YzEzMVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YjQ1MCBcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjMThjXHVjMjE4XHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NzRcdWMxMWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ3MDMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBIFRlcnJpYmx5IEdyaW1tIFByb2JsZW0iLCJkZXNjcmlwdGlvbiI6IjxwPkdyaW1tJnJzcXVvO3MgY29uamVjdHVyZSBzdGF0ZXMgdGhhdCB0byBlYWNoIGVsZW1lbnQgb2YgYSBzZXQgb2YgY29uc2VjdXRpdmUgY29tcG9zaXRlIG51bWJlcnMgb25lIGNhbiBhc3NpZ24gYSBkaXN0aW5jdCBwcmltZSB0aGF0IGRpdmlkZXMgaXQuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBmb3IgdGhlIHJhbmdlIDI0MiB0byAyNTAsIG9uZSBjYW4gYXNzaWduIGRpc3RpbmN0IHByaW1lcyBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6MzYlXCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo0JVwiPjI0MjxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo0JVwiPjI0MzxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo0JVwiPjI0NDxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo0JVwiPjI0NTxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo0JVwiPjI0NjxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo0JVwiPjI0NzxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo0JVwiPjI0ODxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo0JVwiPjI0OTxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo0JVwiPjI1MDxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+NjE8XC90ZD5cclxuXHRcdFx0PHRkPjc8XC90ZD5cclxuXHRcdFx0PHRkPjQxPFwvdGQ+XHJcblx0XHRcdDx0ZD4xMzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzE8XC90ZD5cclxuXHRcdFx0PHRkPjgzPFwvdGQ+XHJcblx0XHRcdDx0ZD41PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG5cclxuPHA+R2l2ZW4gdGhlIGxvd2VyIGFuZCB1cHBlciBib3VuZHMgb2YgYSBzZXF1ZW5jZSBvZiBjb21wb3NpdGUgbnVtYmVycywgZmluZCBhIGRpc3RpbmN0IHByaW1lIGZvciBlYWNoLiBJZiB0aGVyZSBpcyBtb3JlIHRoYW4gb25lIHN1Y2ggYXNzaWdubWVudCwgb3V0cHV0IHRoZSBvbmUgd2l0aCB0aGUgc21hbGxlc3QgZmlyc3QgcHJpbWUuIElmIHRoZXJlIGlzIHN0aWxsIG1vcmUgdGhhbiBvbmUsIG91dHB1dCB0aGUgb25lIHdpdGggdGhlIHNtYWxsZXN0IHNlY29uZCBwcmltZSwgYW5kIHNvIG9uLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgbWF5IGJlIHNldmVyYWwgZGF0YSBzZXRzLjxcL3A+XHJcblxyXG48cD5FYWNoIGRhdGEgc2V0IHdpbGwgY29uc2lzdCBvZiBhIHNpbmdsZSBsaW5lIHdpdGggdHdvIGludGVnZXJzLCBMIGFuZCBIICg0ICZsZTsgTCAmbHQ7IEggJmxlOyAxMDxzdXA+MTA8XC9zdXA+KS4gSXQgaXMgZ3VhcmFudGVlZCB0aGF0IGFsbCB0aGUgbnVtYmVycyBpbiB0aGUgcmFuZ2UgZnJvbSBMIC4uLiBILCBpbmNsdXNpdmUsIGFyZSBjb21wb3NpdGUuPFwvcD5cclxuXHJcbjxwPlRoZSBpbnB1dCB3aWxsIGVuZCB3aXRoIGEgbGluZSB3aXRoIHR3byAwcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCwgcHJpbnQgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHRoZSBzZXQgb2YgdW5pcXVlIHByaW1lcywgaW4gb3JkZXIsIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=