백준 1929 - 소수 구하기(에라토스테네스의 체 활용)

0. 주어진 문제

소수 구하기 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	33432	9395	6565	28.696%

문제

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

입력

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

출력

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

1. 풀이

1) 에라토스테네스 체를 이용하자.

2) 1≤M≤N≤1,000,000인 수가 입력되었을 때, M과 N사이의 소수를 출력해야 하므로 N보다 같거나 작은 범위의 소수를 구해내는 함수를 만들어내자.

3) 소수의 시작인 2부터 자신의 배수를 모두 소거하는 함수를 만들자.

4) 만일 소거를 하는데 기준이 되는 i의 제곱이 N의 범위보다 커진다면 더이상 탐색을 그만한다(왜냐하면, 소거가 되는 수를 살펴보면 자신의 제곱부터 소거가 된다.

 즉, 자신의 제곱이 탐색 범위를 초과한다면 더 이상의 소거는 필요 없어지므로 반복을 계속 하는것은 시간 낭비가 되기 때문이다.)

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#include <iostream>   bool eratosthenes_sieve[1000002];   void count_prime(const int begin, const int end) {     int i, j;       //배열 초기화     for (i = 2; i <= end;i++) {         eratosthenes_sieve[i] = true;     }       //소수 탐색     for (i = 2;i <= end;i++) {         if (i*i >= end)             break;         if (eratosthenes_sieve[i]) {             for (j = i * i;j <= end;j += i)                 eratosthenes_sieve[j] = false;         }              }       //범위 내의 true의 값을 출력     for (i = begin;i <= end;i++) {         if(eratosthenes_sieve[i])             std::cout << i << "\n";     } }   int main() {     int m,n;     std::cin >> m >> n;     count_prime(m, n);       return 0; } Colored by Color Scripter

cs

3. 문제 출처

https://www.acmicpc.net/problem/1929

4. 참고

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4