Leetcode 204번 Count Primes 문제

해당 문제는 아래 링크에서 가져왔습니다: 

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

Count Primes - LeetCode

Leetcode 204번 Count Primes 문제

---

문제 분석

문제를 간단히 읽어보니 소수를 구하는 문제였습니다. 입력받은 숫자까지의 소수의 갯수가 몇개인지를 출력하면 되는 문제입니다. 다만, 주어진 인풋의 범위가 크다는 것이 문제였습니다. ${0 <=n <= 5*10^6}$으로 시간복잡도 ${O(n^2)}으로는 Time Limit이 출력되어 해결할 수 없었습니다. 

위와 같이 ${O(n^1.5)}로 두어도 여전히 같은 에러였습니다. 그러던 중 Hint를 보게 되었고 참고하여 문제없이 풀 수 있었습니다. 

소수는 1과 자기자신으로만 나눌 수 있는 수입니다. 따라서 이전에 봤었던 수를 이용해서 아래 gif처럼 이용할 수 있습니다. 

File:Sieve of Eratosthenes animation.gif - Wikimedia Commons

---

class Solution {
public:
    int countPrimes(int n) {
        if(n == 0)
            return 0 ;
        
        bool isPrime[n] ;
        for (int i = 2; i < n; i++) {
            isPrime[i] = true;
        }
        // Loop's ending condition is i * i < n instead of i < sqrt(n)
        // to avoid repeatedly calling an expensive function sqrt().
        for (int i = 2; i * i < n; i++) {
            if (!isPrime[i]) continue;
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) count++;
        }
        return count;
    }
};

---

해당 코드는 Github에서도 보실 수 있습니다:

https://github.com/gurcks8989/CodingTest/blob/master/LeetCode/P204_Count_Primes.cpp

GitHub - gurcks8989/CodingTest: CodingTest_study_with_c++

훈수 및 조언은 언제든지 환영입니다.