소수 구하기 (에라토스테네스의 체)

소수(Prime Number)는 약수로 1과 자기 자신만을 가지는 정수입니다. 정수론의 기본 정리에 의해 모든 자연수는 단 하나의 소수들의 곱으로 표현됩니다.

1. 기본적인 접근

소수는 1과 N만을 약수로 가진다. 그럼 2부터 N-1까지의 수로는 나눠져서는 안된다.

#include <iostream>
using namespace std;

int main(){
    unsigned int num;
    cout << "소수를 구할 수를 입력하세요 : ";
    cin >> num;
    bool isPrime = true;

    // 2부터 N-1의 수로 나눠서 나눠지는 수가 있으면 반복문 종료
    for (int i=2; i<num; i++) {
        if (num % i == 0) {
            isPrime = false;
            break;
        }
    }

    if(isPrime) {
        cout << num << "은 소수입니다." << endl;
    }
    else {
        cout << num << "은 소수가 아닙니다." << endl;
    }

    return 0;
}

연산 횟수 : N-2번

2. 에라토스테네스의 접근

주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다. 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 N의 제곱근 이하이기 때문이다.

즉, 2부터 N의 제곱근 까지 나눠보면 됩니다.

#include <iostream>
#include <math.h>
using namespace std;

int main(){
    unsigned int num;
    cout << "소수를 구할 수를 입력하세요 : ";
    cin >> num;
    bool isPrime = true;

    // 2부터 N의 제곱근까지의 수로 나눠서 나눠지는 수가 있으면 반복문 종료
    for (int i=2; i<=sqrt(num); i++) {
        if (num % i == 0) {
            isPrime = false;
            break;
        }
    }

    if(isPrime) {
        cout << num << "은 소수입니다." << endl;
    }
    else {
        cout << num << "은 소수가 아닙니다." << endl;
    }

    return 0;
}

연산 횟수 : 루트(N-2) 번

3. 에라토스테네스의 체

에라토스테네스의 체는 매우 간단한 아이디어입니다. 위에서 모든 자연수는 소수들의 곱으로 표현이 된다고 했습니다. 제일 작은 소수 2부터 시작합니다. 2부터 N-1까지의 수 중에서 2의 배수를 모두 체로 거르고 남은 숫자들 중에서 3의 배수로 거르고를 반복해서 제곱근N 까지 나눠서 걸러지지 않고 남은 수들이 모두 소수가 됩니다.

#include <iostream>
#include <math.h>
using namespace std;

int main(){
    unsigned int num;
    cout << "소수를 구할 수를 입력하세요 : ";
    cin >> num;

    bool* prime = new bool[num+1];
  	memset(prime, 0, sizeof(bool) * (num + 1));

    for (int i=2; i<=num; i++) {
        if (prime[i] == false) {
            for (int j=i*2; j<=num; j+=i) {
                prime[j] = true;
            }
        }
    }

  	for (int i=0; i<=num; i++) {
        prime[i] = !prime[i];
    }

    if(prime[num]) {
        cout << num << "은 소수입니다." << endl;
    }
    else {
        cout << num << "은 소수가 아닙니다." << endl;
    }

    return 0;
}

주어진 수가 소수인지 아닌지 판별만 할 경우는 2번째 방법을 사용하는 것이 좋습니다.
그러나 다음 문제처럼 주어진 수 까지의 모든 소수를 구하기 위해서는 에라토스테네스의 체를 사용합니다.

 

다시 한번 간단하게 에라토스테네스의 체를 정리하며 마무리 하겠습니다.

prime[10000];

for (int i = 2; i < 10000; i++) {
  if (prime[i] == false) {
    for (int j = i*2; j < 10000; j += i) {
      prime[j] = true;
    }
  }
}

for (int i = 0; i < 10000; i++) {
  prime[i] = !prime[i];
}

 

참고 : 에라토스테네스의 체 - 위키백과

출처 : https://jongmin92.github.io/2017/11/05/Algorithm/Concept/prime/#2-에라토스테네스의-접근