[C++] 소수 구하기 (에라토스테네스의 체)

보통 소수라 하면, 1과 자기자신을 제외하고는 나누어 떨어지지 않는 수라고 불린다.

이를 구하기 위해서 하나 하나씩 나누어 떨어지는 지 검사를 하고는 했는데

더 빠르게 구할 수 있는 방법이 있다.

바로

'에라토스테네스의 체' 라는 알고리즘을 사용하는 것이다.

에라토스테네스의 체는, 미리 범위를 정하여 소수인지 아닌지 구하여

배열에 저장을 한 뒤에, 일반적으로 사용이 된다.

로직은 다음과 같다.

1은 소수가 아니다.

2는 소수이다. -> 2의 배수는 소수가 아니다.

3은 소수이다. -> 3의 배수는 소수가 아니다.

4는 소수가 이미 아니다.

5는 소수이다. -> 5의 배수가 소수가 아니다.

... (반복)

식으로 구현이 가능하며, boolean 값을 가지는 check 배열을 사용하여

반복문을 돌려준다.

1. 1의 소수가 아니다.

2. 이미 소수가 아닌 값은 제외를 시켜준다.

3. 소수의 배수는 소수가 아니다.

4. 더 나눌 필요 없다. sqrt(end)까지 반복한다. (이유는 아직 잘 모르겠지만, 수학자들이 증명하셨답니다)

( 4.22 수정)
qrt(end)까지만 반복하는 이유는!!
소수는 n의 배수가 아니어야 하므로, 입력받은 수를 입력받은 수보다 작은 수들로 나누어서 떨어지면 소수가 아닙니다.
이 때, 수가 수를 나누면 몫이 발생하게 되는데, 몫과 나누는 수 둘 중 하나는 반드시 sqrt(end) 이하가 됩니다.
따라서, 모두 나누어볼 필요없이 sqrt(end) 까지만 나누어 보면 됩니다.

소스코드

#include<iostream>
// Sieve of Eratosthenes
using namespace std;
int main(){
    int begin, end;
    scanf("%d",&begin);
    scanf("%d",&end);
 
    // 소수이면 false
    // 소수가 아니면 true이다    
    bool *c = new bool[end+1];
    c[1] = true;
    for(int i = 2; i*i<= end; i++){
        if(c[i] == false){
            for(int j = i * i; j <= end; j+=i){
                c[j] = true;
            }
        }
    }
    for(int i = begin; i <= end; i++)
        if(c[i] == false)
            printf("%d\n",i);
    delete c;
    return 0;
}

소스코드2 (visual studio)

#include<iostream>
#include<vector>
using namespace std;
 
int begin_, end_;
vector<bool> check;
 
int main() {
   cin >> begin_ >> end_;  
 
   check.resize(end_ + 1);
 
   check[1] = true;
   for (int i = 2; i * i <= end_; i++) {
      if (!check[i]) {
         for (int j = i + i; j <= end_; j += i) {
            check[j] = true;
         }
      }
   }
   for (int i = begin_; i <= end_; i++)
      if (!check[i])
         cout << i << '\n';
 
   return 0;
}

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.