[leetcode] 204. Count Primes - C

문제

https://leetcode.com/problems/count-primes/submissions/

Count Primes - LeetCode

• 분류 - ?
• 난이도 - Medium
• 제약조건 - 0 <= n <= 5 * 10^6

 

 

---

문제 설명

n이 주어졌을 때, n보다 작은 소수의 수를 구하는 문제.

주어진 제약조건은 0 <= n <= 5 * 10^6 이므로, O(NlogN) 이하의 시간복잡도를 가져야 한다.

---

관련 개념

에라토스테네스의 체

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

가장 접근하기 쉬운 브루트포스 방법을 사용하면 (1~n까지의 경우의 수 i)*(1~i까지의 경우의 수)를 연산하게 되어 시간복잡도가 O(N^2)이 된다.

시간복잡도를 줄이기 위해 에라토스테네스의 체를 사용할 수 있는데, (1~n의 제곱근까지의 경우의 수 i)*(i*i~n까지의 경우의 수)를 연산하게 되므로 시간복잡도를 O(NlogN)으로 줄일 수 있다.

---

답안 코드1 - 브루트포스

Time Limit Exeeded - 17 / 66 test cases passed.

• 시간복잡도: O(N^2)

int countPrimes(int n){
    int cnt=0;
    int nums={}
    for(int i=2; i<n; i++){
        if(i == 2){
            cnt++;
            continue;
        }
        for(int j=2; j<i; j++){
            if(i%j == 0) break;
            if(j == i-1) cnt++;
        }
    }
    return cnt;
}

 

답안 코드2 - 에라토스테네스의 체

Runtime: 296 ms, Memory Usage: 27.5 MB

• 시간복잡도: O(NlogN)

int countPrimes(int n){
    int cnt=0;
    if(n==0 || n==1) return 0;
    int nums[n];
    
    for(int i=2; i<n; i++){
        nums[i] = 1; // 1-소수, 0-소수 아님
    }
    
    for(int i=2; i*i<n; i++){
        if(nums[i]){
            for(int j=i*i; j<n; j+=i){
                nums[j] = 0;
            }
        }
    }
    
    for(int i=2; i<n; i++){
        if(nums[i] == 1) cnt++;
    }
    
    return cnt;
}