[레벨1] 소수찾기 - 에라토스테네스의 체

에라토스테네스의 체 

n의 수까지 소수를 구하는 알고리즘이다.

위 그림은 120까지의 소수를 구하는 그림인데 그림을 보아도 어떻게 진행이 될지 예상이 간다.

 

과정은 간단하다.

 

1. n + 1의 크기의 배열을 만들어준다. (초기화도 진행)

2. 2부터 n의 제곱근 까지 반복을 돌면서 해당하는 수(반복문의 i)의 배수에 해당하는 수를 체크한다.

 -> 제곱근을 구하는 이유는 2중 반복문(j라고 가정)에서 j는 i의 배수만큼 증가하면서 배열의 요소를 체크.

3. 체크되지 않은 수가 소수

 

#include <string>
#include <cmath>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<bool> primeCount(n + 1); // 0(false)로 초기화
    primeCount[1] = true; // 1은 소수가 아니다
    int num = sqrt(n); // 제곱근
    for(int i = 2; i <= num; ++i)
    {
        if(primeCount[i]) continue; // 체크된것은 패스. 이미 소수가아님.
        for(int j = i + i; j <= n; j += i) // 배수증가
        {
            primeCount[j] = true;
        }
    }
    // 소수찾기 완료
    
    for(int i = 2; i <= n; i++)  // 소수체크
	    if(!primeCount[i]) // 아직도 0인 요소가 소수가 아님.
            ++answer;
    return answer;
}