시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB4912619.355%

문제

행운 수(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 …

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

입력

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

출력

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

예제 입력 1

1 8

예제 출력 1

1
3
7
9
13
15
21
25

예제 입력 2

200000 200010

예제 출력 2

3022281
3022311
3022321
3022323
3022335
3022341
3022351
3022371
3022393
3022399
3022405

예제 입력 3

3000000 3000000

예제 출력 3

54790233

힌트

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

출처