시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cdWM1ZjBcdWMxOGRcdWI0MWMgXHVkNTY5XHVjMTMxXHVjMjE4XHVjNzU4IFx1YWQ2Y1x1YWMwNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjMDFcdWFjMDFcdWM3NTggXHVkNTY5XHVjMTMxXHVjMjE4XHViOTdjIFx1YjA5OFx1YjIwYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMThjXHVjMjE4XHViOTdjIFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWMxOGNcdWMyMThcdWI5N2MgXHViYzMwXHVjZTU4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWI3N2NcdWJhNzQsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMThjXHVjMjE4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViN2VjXHVkNTVjIFx1YWM4M1x1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHViNzdjXHViYTc0LCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzE4Y1x1YzIxOFx1YWMwMCBcdWM3OTFcdWM3NDBcdWFjODMsIFx1YzEzOCBcdWJjODhcdWM5ZjgsLi4uIFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjMmRkXHVjNzNjXHViODVjIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHViYzI5XHViYzk1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBMXHVhY2ZjIEhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoNCAmbGU7IEwgJmx0OyBIICZsZTsgMTA8c3VwPjEwPFwvc3VwPik8XC9wPlxyXG5cclxuPHA+XHVkNTZkXHVjMGMxIEwuLi4gSFx1YWQ2Y1x1YWMwNFx1Yzc1OCBcdWMyMThcdWIyOTQgXHVkNTY5XHVjMTMxXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHViNDUwIFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWMxOGNcdWMyMThcdWI5N2MgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU3NFx1YzExYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDcwMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkEgVGVycmlibHkgR3JpbW0gUHJvYmxlbSIsImRlc2NyaXB0aW9uIjoiPHA+R3JpbW0mcnNxdW87cyBjb25qZWN0dXJlIHN0YXRlcyB0aGF0IHRvIGVhY2ggZWxlbWVudCBvZiBhIHNldCBvZiBjb25zZWN1dGl2ZSBjb21wb3NpdGUgbnVtYmVycyBvbmUgY2FuIGFzc2lnbiBhIGRpc3RpbmN0IHByaW1lIHRoYXQgZGl2aWRlcyBpdC48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGZvciB0aGUgcmFuZ2UgMjQyIHRvIDI1MCwgb25lIGNhbiBhc3NpZ24gZGlzdGluY3QgcHJpbWVzIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDozNiVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjQlXCI+MjQyPFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjQlXCI+MjQzPFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjQlXCI+MjQ0PFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjQlXCI+MjQ1PFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjQlXCI+MjQ2PFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjQlXCI+MjQ3PFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjQlXCI+MjQ4PFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjQlXCI+MjQ5PFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjQlXCI+MjUwPFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD42MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+NzxcL3RkPlxyXG5cdFx0XHQ8dGQ+NDE8XC90ZD5cclxuXHRcdFx0PHRkPjEzPFwvdGQ+XHJcblx0XHRcdDx0ZD4zMTxcL3RkPlxyXG5cdFx0XHQ8dGQ+ODM8XC90ZD5cclxuXHRcdFx0PHRkPjU8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcblxyXG48cD5HaXZlbiB0aGUgbG93ZXIgYW5kIHVwcGVyIGJvdW5kcyBvZiBhIHNlcXVlbmNlIG9mIGNvbXBvc2l0ZSBudW1iZXJzLCBmaW5kIGEgZGlzdGluY3QgcHJpbWUgZm9yIGVhY2guIElmIHRoZXJlIGlzIG1vcmUgdGhhbiBvbmUgc3VjaCBhc3NpZ25tZW50LCBvdXRwdXQgdGhlIG9uZSB3aXRoIHRoZSBzbWFsbGVzdCBmaXJzdCBwcmltZS4gSWYgdGhlcmUgaXMgc3RpbGwgbW9yZSB0aGFuIG9uZSwgb3V0cHV0IHRoZSBvbmUgd2l0aCB0aGUgc21hbGxlc3Qgc2Vjb25kIHByaW1lLCBhbmQgc28gb24uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGVyZSBtYXkgYmUgc2V2ZXJhbCBkYXRhIHNldHMuPFwvcD5cclxuXHJcbjxwPkVhY2ggZGF0YSBzZXQgd2lsbCBjb25zaXN0IG9mIGEgc2luZ2xlIGxpbmUgd2l0aCB0d28gaW50ZWdlcnMsIEwgYW5kIEggKDQgJmxlOyBMICZsdDsgSCAmbGU7IDEwPHN1cD4xMDxcL3N1cD4pLiBJdCBpcyBndWFyYW50ZWVkIHRoYXQgYWxsIHRoZSBudW1iZXJzIGluIHRoZSByYW5nZSBmcm9tIEwgLi4uIEgsIGluY2x1c2l2ZSwgYXJlIGNvbXBvc2l0ZS48XC9wPlxyXG5cclxuPHA+VGhlIGlucHV0IHdpbGwgZW5kIHdpdGggYSBsaW5lIHdpdGggdHdvIDBzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0LCBwcmludCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIHNldCBvZiB1bmlxdWUgcHJpbWVzLCBpbiBvcmRlciwgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==