[C] LeetCode 204. Count Primes

 

문제(원문)

문제(번역)

정수 n이 주어질때, 정수 n보다 작은 소수의 개수를 구해라.

접근 방법

소수 구하는 문제는 거의 에라토스테네스의 체를 활용하면 된다.

에라토스테네스의 체란 2부터 시작해서 각 소수의 배수를 차례대로 지워가면서 소수만 남기는 방식이다.

어떤 수 i가 소수이면 i의 배수는 전부 합성수가 되기 때문이다. 보통 \(i^2\) 부터 지우면 이미 처리된 수를 건너 뛰게 되어 더 효율적이다.

 

해당 문제에서도 에라토스테네스의 체를 활용했다. 메모리 사용량을 더 줄이기 위해 동적할당을 사용해 체에 필요한 리스트를 할당했다.

 

소스 코드

int countPrimes(int n) {
    if(n<=2) return 0;
    char* arr = (char*)malloc(n+1);
    memset(arr, 1, n+1);
    arr[0] = 0; arr[1] = 0;
    for(int i =2; i*i<n;i++) {
        if(arr[i]==1) {
            for(int j=i*i; j<n;j+=i) {
                arr[j] = 0;
            }
        }
    }
    int count=0;
    for(int i=2; i<n;i++) {
        if(arr[i]==1) count++;
    }
    return count;
}