소수 찾기 (에라토스테네스의 체)

주어진 숫자 하나가 소수인지 아닌지 판단하는 함수

2부터 N까지 전부 순회하면서 isPrime이 true를 반환하면 개수가 증가하는 방식이다. √num까지만 확인해 봐도 충분하다.

하지만 N이 100만 정도라면, 이 방식은 O(N√N)이라서 느릴 수 있다.

class Solution {
    static boolean isPrime(int num) {
        if (num < 2) return false;
        for (int i=2; i*i<=num; i++)
            if (num % i == 0) 
                return false;
    }

    public int solution(int n) {
        int cnt = 0;
        for (int i=2; i<=n; i++)
            if (isPrime(i)) cnt++;
        return cnt;
    }
}

---

에라토스테네스의 체

성능을 고려하면 에라토스테네스의 체가 더 효율적이다. 이는 boolean 배열 기반의 함수로 구현한다.

에라토스테네스의 체가 무엇인지 궁금하다면? https://www.youtube.com/watch?v=oYj_rwUpncM

 

에라토스테네스의 체는 O(NloglogN)​의 시간복잡도를 가진다. (O(NloglogN) 정도면 O(N)이랑 비슷하지만 약간 더 느린 정도로, 거의 선형에 가깝다고 한다. 극한의 효율!)

class Solution {
    public int solution(int n) {
        // 에라토스테네스의 체
        boolean[] isNotPrime = new boolean[n+1];
        for (int i=2; i*i<=n; i++)
            if (!isNotPrime[i])
                for (int j=i*i; j<=n; j+=i)
                    isNotPrime[i] = true;
        
        int cnt = 0;
        for (int i=2; i<=n; i++)
            if (!isNotPrime[i]) cnt++;
        return cnt;
    }
}