[릿코드] 204번 : Count Primes

leetcode.com/problems/count-primes/

Count Primes - LeetCode

 

---

 

문제

n보다 작은 수 중에서 소수의 개수를 구하시오

소수 : 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 

ex) 5 => 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수

 

어떻게 풀까

에라토스테네스의 체라는 소수판별 알고리즘을 사용해 문제를 풀자

 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.

2. 2는 소수이므로 오른쪽에 2를 쓴다.

3. 자기 자신을 제외한 2의 배수를 모두 지운다.

4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.

5. 자기 자신을 제외한 3의 배수를 모두 지운다.

6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.

7. 자기 자신을 제외한 5의 배수를 모두 지운다.

8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다.

9. 자기 자신을 제외한 7의 배수를 모두 지운다.

10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

출처 : 위키백과

 

 

이렇게 2부터 시작해서 소수면 따로 표시를 하고, 

그 수의 배수들은 모두 소수 후보에서 제외하는 방식을 사용한다

 

2부터 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 소수를 구할 수 있다.

 

번외 - 왜 제곱근인가?

 

특정한 숫자 = NUM

NUM = X x Y (X >= Y) 이라고 가정하자

 

X x X >= X x Y (NUM)이 성립한다.

-> X^2 >= NUM 

-> X >= NUM^1/2

 

따라서 최소값은 Num^1/2가 되기 때문에 제곱근까지만 구하면 되는것이다.

 

출처 : 에라토스테네스의 체

 

구현 중 만난 문제/해결

for문 두개를 사용해 문제를 풀려고 했으나 time limit exceeded가 뜨며 통과하지못했다.

public int countPrimes(int n) {

  int result = 0;
  for (int i=2; i<n; i++) {
    if (i == 2) result++;
    if (i%2==0) continue;
    for (int j=2; j<i; j++) {
      if (i % j == 0) break;
      else if (j == i-1) result++;
    }
  }

  return result;
}

 

검색을 통해 소수판별 알고리즘인 에라토스테네스의 체를 알게 되었다.

 

구현

 

class Solution {
    public int countPrimes(int n) {

        int result = 0;
        boolean[] isPrime = new boolean[n+1];
        Arrays.fill(isPrime, true);

        for( int i=2; i<n; i++) {
            for(int j=i*2; j<n; j+=i) {
                isPrime[j] = false;
            }
        }

        for(int i=2;i<n;i++){
            result += isPrime[i] ? 1: 0;
        }

        return result;
    }
}