[BOJ] 1929 소수 구하기 - 에라토스테네스의 체

문제

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

입력

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

출력

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

예제 입력 1 

3 16

예제 출력 1 

3
5
7
11
13

소수를 구하는 프로그램은 많지만 이번에는 그 중 가장 최적화된 알고리즘으로 알려져있는 에라토스테네스의 체 알고리즘으로 풀어야만 시간초과가 나지 않는 문제를 풀어봤다. 에라토스테네스의 체란 2의 배수를 거르고, 3의 배수를 거르고, 차례대로 수의 배수를 걸러내는 알고리즘이다.



저명하게 알려져있는 알고리즘은 배열에 2부터 구하는 범위까지의 수를 배열에 저장하고 체에 걸러내는 식이었는데 나는 M에서 N 까지의 소수를 구해야하기 때문에 M부터 배열에 저장하는 식으로 풀려고 했다. 하지만 내생각에 이렇게는 구현이 쓸데없이 복잡해지는 것 같다.

제출한 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#include <iostream> #include <cmath> using namespace std; int main(){     int m,n;     cin>>m>>n;     int *arr = new int[n+1];     for(int i=2;i<=n;i++){         arr[i]=i;     }     for(int i=2;i<=sqrt(n);i++){         if(arr[i]==0) continue;         for(int j=i+i;j<=n;j+=i)             arr[j]=0;     }     for(int i=m;i<=n;i++){         if(arr[i]!=0)             cout<<arr[i]<<'\n';     } }

cs