소수값 구하기 - 에라토스테네스의 체

 

소수를 찾는 방법 중 에라토스테네스의 체 방법을 설명드리겠습니다.

시간복잡도: O(NloglogN)

에라토스테네스의 체 원리

1. 2부터 120(예시)까지 모든 숫자를 나열합니다. (1은 소수가 아니므로)

2. 숫자 하나씩 방문하면서 자기자신을 제외한 배수를 제거합니다. (2를 방문했다면 2를 제외한 배수 4부터 지우기)

3.  bool함수를 이용해 전에 지웠던 숫자를 다시 방문하지 않게 합니다.

 

 

소수만 출력하는 코드

#include<iostream>
const int INF = 10001;

int arr[INF];
bool primearray[INF];

void Eratos(int n)
{
    if (n <= 1)
        return;
    for(int i = 2; i * i <= INF; i++)
    {
        if(primearray[i])
        {
            for(int j = i * i; j <= INF; j += i)
            {
                primearray[j] = false;
            }
        }
    }
}

int main()
{
    //초기화
    for(int i = 0; i < INF + 1; i++)
    {
        arr[i] = i;
        primearray[i] = true;
    }
    
    Eratos(INF);

    for(int i=2; i<INF; i++)
    {
        if(primearray[i])
            std::cout << arr[i] << " ";
    }
}

 

for (int i = 2; i * i <= INF; i++) 에서 i * i인 이유

 

어떤 숫자 N이 있다고 가정하겠습니다.

N = a * b 이고 n 은 N의 제곱근이라 하고 a >= n 이면

a * b = N = n * n 이므로 b <= n 가 됩니다.
따라서 "N의 제곱근"까지만 검사를 하면 b까지는 충분히 체크할 수 있고, a*b의 쌍이 없다면 소수라고 할 수 있습니다.

 

 

출력값

   ...