[C++] 프로그래머스 소수 찾기 (with 에라토스테네스의 체)

programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기

 

1. 서론

 

level 1의 간단한 줄 알았는데 아닌 문제. 일반적인 소수 찾기 식으로는 풀 수 없다!

 

2. 문제 풀이

 

어떤 숫자가 입력된다. 1과 그 숫자 사이에 있는 숫자의 개수를 반환하는 코드를 짜야한다. 그 숫자의 범위는 2부터 백만까지이다.

그래서 우리가 일반적으로 알고 있는 소수를 구하는 코드로는 효율성을 맞출 수 없다. 

처음에는 그렇게 풀었는데 테스트 케이스의 절반 정도가 시간초과로 실패했다.

그래서 이 문제에 대해 찾아보니 소수를 구하는데 가장 최적의 방법인 '에라토스테네스의 체'를 이용해서 풀어야 했다.

 

 

에라토스테네스의 체란?

 

에라토스테네스의 체 원리 설명

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 

출처: ko.wikipedia.org/wiki/에라토스테네스의_체

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

소수를 구하는 동시에 그 소수의 배수를 전부 소수에서 제외하면서 범위를 좁혀가며 소수를 구할 수 있는 이론이다. 

기존의 소수를 구하는 방식이라면 for문을 두 번 돌려야 하기 때문에 시간 복잡도가 O(n^2)라서 효율성이 터진다...

하지만 에라토스테네스의 체를 쓰면 범위가 계속 줄기 때문에 시간복잡도가 O(n log log n)이라고 한다...

 

3. 코드 작성

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0, i, j;
    bool* a = new bool[n + 1];
    
    for (i = 2; i <= n; i++)
        a[i] = true;
    
    for (i = 2; i * i <= n; i++)
        if (a[i])
            for (j = i * i; j <= n; j += i)
                a[j] = false;
    
    for (i = 2; i <= n; i++)
        if (a[i])
            answer++;
    
    return answer;
}

 

a는 boolean 형식의 배열이다. 2부터 n까지를 전부 true로 초기화한다.

그리고 2부터 n까지 탐색하면서 a[i] 가 true, 즉 소수인 경우에는 그 배수들을 전부 false로 만든다. 즉, 범위에서 제외하는 것이다.

이렇게 2~n까지 한 바퀴 돌고나면 소수와 소수가 아닌 수가 나뉘게 된다. 

a [i]가 true인 경우만 count 해서 소수의 개수가 몇 개 인지 구한다.

 

 

소수 구하기에 많이 쓰인다고 하니 외워두는 게 좋을 것 같다. 좋은 거 하나 배우네요....