행운 수 구하기

행운 수(Lucky numbers)는 에라토스테네스의 체와 비슷한 방법으로 만들어지는 자연수의 부분집합 또는 그 부분집합의 원소를 말한다.

행운 수의 집합은 다음과 같은 과정을 통해 구성할 수 있다.

1. 홀수 자연수의 목록을 만든다.
2. 목록에 속한 수 중 1보다 크면서 선택한 적이 없는 수 중에서 가장 작은 수를 선택한다.
3. 2.에서 선택한 자연수를 k라고 할 때, 목록에서 오름차순으로 i×k (i ≥ 1) 번째에 해당하는 모든 자연수를 지운다.
4. 2.로 돌아간다.

다음은 위 과정의 일부를 수행하는 예시이다.

1. 1 3 5 7 9 11 13 15 17 19 21 23 25 …
2. 1 3 5 7 9 11 13 15 17 19 21 23 25 …
3. 1 3 5 7 9 11 13 15 17 19 21 23 25 …
4. 1 3 7 9 13 15 19 21 25 …
5. 1 3 7 9 13 15 19 21 25 …
6. 1 3 7 9 13 15 19 21 25 …
7. 1 3 7 9 13 15 21 25 …
8. 1 3 7 9 13 15 21 25 …
9. …

두 개의 자연수 L과 R이 주어지면 L번째부터 R번째까지의 행운 수를 알아보자.

첫째 줄에 두 개의 자연수 L과 R이 주어진다. (1 ≤ L ≤ R ≤ 3,000,000 = 3 × 106, R - L ≤ 100,000 = 105)

R - L + 1개의 줄에 걸쳐 i번째 줄에 L + i - 1번째 행운 수를 출력한다.

모든 가능한 입력에 대해서 R번째 행운 수와 L번째 행운 수의 차이는 2,000,000 (2 × 106)보다 작다.