[C++] 소수 구하는 알고리즘 - 에라토스테네스의 체

프로그래머스 level 1의 '소수 찾기' 문제를 풀면서 알게 된 '에라토스테네스의 체'에 대해 정리해보았다.

에라토스테네스의 체
: 대량의 소수들을 빠르게 구할 수 있는 방법

에라토스테네스의 체를 알기 전 내가 처음 시도했던 방법

처음에는 숫자 n이 소수인지 아닌지 판별하기 위해서 2부터 숫자 n의 절반만큼만 반복문을 돌면서 n을 나눈 나머지가 0이 되는 값이 있는지 확인했다.

bool checkPrime(int n) {
	for (int i = 2; i * i <= n; i++) {
    	if (n % i == 0) return false;
    }
    
    return true;
}

이렇게 소수인지 아닌지를 판별하는 함수를 만들어서 문제를 해결하려했는데, 정확성 테스트는 통과하지만 효율성 테스트가 0점이었다...😭

효율성을 높이려면 어떤 방식을 사용해야하나 고민하다가 '질문하기' 탭에 들어가서 사람들이 질문한 목록들을 쭉 살펴보니...

'에라토스테네스의 체'라는 말이 계속 언급되고 있었다.

에라토스테네스의 체

소수들을 구할 값의 범위만큼 배열을 만들고, 그 배열을 순회하면서 자신을 제외한 배수는 지우면서 소수를 구하는 방법이다.

예를 들어서, 1부터 10까지의 숫자 중 소수인 숫자들만 구한다고 한다면!

1. 크기 n(=10)인 배열을 만들어서 각 인덱스에 값을 넣어준다!

int arr[n+1];

for (int i = 2; i <= n; i++) {
	arr[i] = i;
}

1은 소수가 아니니까 반복문은 2부터 시작해줬고, n번째 인덱스에 n을 넣을 거기 때문에 배열은 n+1 크기로 할당해주었다.

2. 배열을 순회하면서 자신을 제외한 배수는 지운다!

for (int i = 2; i <=n; i++) {
	if(arr[i] == 0) continue;
    
    for (int j = i + i; j <= n; j += i) {
    	arr[j] = 0;
    }
}

배수에 해당하는 인덱스 값들을 0으로 바꿔줌으로써 지워준다.

이렇게 하면 배열에 소수가 아닌 수들은 0, 소수인 수들은 그 값 자체가 들어가있게 된다!!

'소수 찾기' 문제 풀이

위 방법을 이용해서 문제를 풀려했는데 효율성 테스트 1이 시간 초과로 실패되고 말았다..!

for (int i = 2; i <= n; i++) {
	if (arr[i] != 0) answer++;
}

return answer;

이렇게 for문을 돌면서 0이 아니면 answer++ 해주고 리턴해주었는데...

생각해보니 굳이 for문을 또 만들어서 answer++을 해줄 필요가 없었다.

두 번째 for문에서 바로 answer++을 해주면 시간을 줄일 수 있다...! 😶

for (int i = 2; i <=n; i++) {
	if(arr[i] == 0) continue;
    
    for (int j = i + i; j <= n; j += i) {
    	arr[j] = 0;
    }
    
    answer++;
}

바로 이렇게! 배수에 0을 넣어주고 answer++을 해주면 되는 것이었다....🙂

전체 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int n) {
    int answer = 0;
    int num[n+1];
    vector<int> prime;
    
    for (int i = 2; i <= n; i++) {
        num[i] = i;
    }
    
    for (int i = 2; i <= n; i++) {
        if (num[i] == 0) continue;
        
        for (int j = i + i; j <= n; j += i) {
            num[j] = 0; 
        }
        
        answer++;
        
    }
        
    return answer;
}