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

프로그래머스 소수 찾기 문제를 풀다가 최적의 알고리즘을 찾기 시작했다. 

내가 푸는 방법으로는 실패가 떠서 찾기 시작했다. 

 

에라토스테네스의 체 (Sieve of Eratosthenes) 라는 알고리즘을 공부 해보도록 하겠다.

위키백과에 설명이 잘 되어있다. 

 

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

위의 그림처럼 1부터 120 사이에 소수를 구해보자!

소수는 1과 자기 자신으로만 나누어지는 수를 의미한다. ( 1은 소수가 아니다.)

 

2부터 120까지 표에 적어넣고 소수가 아닌것을 모두 체크 한다.

 

2는 소수이다. 그럼 2의 배수를 체크한다.

3은 소수이다. 그럼 3의 배수를 체크한다.

4는 2의 배수에서 체크했으니깐 제외

5는 소수이다. 그럼 5의 배수를 체크한다.

6은 2의 배수에서 체크했으니깐 제외

........

체크가 안된 수들이 소수이다.

 

그럼 구현을 해보자.

 

cpp 구현

#include <iostream>

using namespace std;

void getPrimeNumber(int num)
{
    int *arr;
    arr = new int[num+1]; // 인덱스가 0부터 시작이니깐 1을 더해주었다.
    int i = 2;
    // 입력받은 수 만큼 배열에 모두 초기화 해둔다
    for (i = 2; i <= num; i++)
    {
        arr[i] = i;
    }

    for (i = 2; i <= num; i++)
    {
        if (arr[i] == 0) // 이미 체크된 수의 배수는 확인하지 않는다
            continue;
        for (int j = i + i; j <= num; j += i)
        { // i를 제외한 i의 배수들은 0으로 체크
            arr[j] = 0;
        }
    }
    
    // print
    for (i = 2; i <= num; i++)
    {
        if (arr[i] != 0)
            cout << arr[i] << " ";
    }
}

int main(void)
{
    clock_t start, end;
    start = clock();

    getPrimeNumber(50000);
    end = clock();

    double time = (double)(end - start) / CLOCKS_PER_SEC;
    cout << "수행시간 : " << time << endl;
}

 

내가 생각하는 단점 !! : 배열 공간을 잡아야하고, 초기화를 해야한다. 이게 단점이지 않을까? 라는 생각을 했다.