코딩테스트 : 소수 찾기

문제 설명

해당 문제는 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 구하는 문제다.
소수는 1과 자기 자신만을 약수로 가지는 2 이상의 자연수를 의미한다.

 

핵심 방법

n이 매우 크기에 에레스토테네스의 체를 사용해 효율적으로 계산한다.

소수 판별은 2부터 √n까지만 해도 충분하다.( √n 이하 소수 * √n  이상은  = n 이기에 √n  이하만 알면 √n  이상도 알 수 있다.  )

i의 배수들은 i*i부터 시작해 j += i로 지워나간다.

vector<bool>을 활용해 메모리를 절약하고 빠르게 연산한다.

 

에레스토테네스의 체에 대해 자세한 설명은 아래 링크에 정리해두었다.

에레스토테네스의 체

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n) {
    // 0부터 n까지의 인덱스를 사용하는 크기 n+1짜리 배열을 생성하고, 모두 true로 초기화
    vector<bool> isPrime(n + 1, true);

    // 0과 1은 소수가 아니므로 false로 설정
    isPrime[0] = false;
    isPrime[1] = false;

    // 2부터 sqrt(n)까지의 숫자만 검사하면 충분하다
    for (int i = 2; i * i <= n; i++) {
        // 현재 수 i가 소수인 경우에만 배수 제거 작업 수행
        if (isPrime[i]) {
            // i의 배수들은 소수가 아니므로 false로 마킹
            // i*i부터 시작하는 이유는 그 이전의 배수들은 이미 지워졌기 때문
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    // 남아있는 true 값의 개수가 곧 소수의 개수
    return count(isPrime.begin(), isPrime.end(), true);
}