[BOJ][C++] 백준 1929번 소수 구하기

1929 소수 구하기

1. 문제 정보

백준 온라인 저지 [1929번 소수 구하기] 문제의 링크입니다.

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000)

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력1

3 16

예제 출력1

3
5
7
11
13

시간 / 메모리 제한

2초 / 256MB

---

2. 생각

1. 문제 1978번을 풀었던 방법(주어진 수가 소수인지 아닌지 판별하는 문제)으로 접근하려고 했습니다.(시간 초과 ㅠㅠ)
   그러나 문제 1929번은 주어진 수 보다 작거나 같은 모든 수가 소수인지 아닌지 판별하는 문제입니다.
   그 결과 시간 복잡도가 O(n루트n)인 알고리즘에 최대 입력값 1,000,000을 대입하면 1,000,000,000(10억) = 10초가 걸려 시간초과가 납니다.

2. 이 문제는 에라토스테네스의 체 방법을 사용해야합니다.

   • 에라토스테스의 체는 2부터 주어진 숫자보다 작은 배열에서
   • 가장 작은 수부터 시작하여 반복합니다. 그 수의 배수를 지워나가는 것입니다.
   • 지워지지 않은 남은 숫자는 모두 소수입니다.

초기 배열 (2~16)

	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

1단계) 2의 배수 삭제

	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

2단계) 3의 배수 삭제

	2	3
5		7
9		11
13		15

최종 결과

	2	3
5		7
		11
13			…

최종 결과 배열에서 입력값인 3~16의 숫자를 출력하면 됩니다.

---

3. 소스코드 (C++)

---

터미널의 입출력 화면 예제1

터미널의 입출력 화면 다른 예제

---

References.

https://ko.wikipedia.org/wiki/에라토스테네스의_체 https://jaimemin.tistory.com/954