Today I Learned

오늘도 자바 코테 공부!

Count Primes

Leetcode 204번 https://leetcode.com/problems/count-primes/description/

문제

Given an integer n, return the number of prime numbers that are strictly less than n.

• 입력
  Input: n = 10
• 출력
  4
  Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

문제 풀이

• n이 주어지면 n보다 작은 소수의 개수를 세는 간단한 문제이다. 소수문제를 푸는 방법은 여러가지이지만 과거에 TIL #156에서 공부했던 에라토스테네스의 체를 이용해 풀었다.

1. 일단 n까지의 모든 수를 소수로 가정하고 초기화한다. isPrime 배열은 해당 인덱스가 소수인지 나타내는 boolean 배열로 쓴다. 일단 0,1은 소수가 아니므로 false로 두고 반복문을 2부터 true로 만든다.

2. 에라토스테네스의 체 알고리즘은 제곱근을 이용해서 반복문 범위를 최적화 한다. 기본적으로 소수의 배수들을 다 소수에서 제외하는 방식이므로 바깥 반복문은 int i = 2; i i < n 범위로, 안쪽 반복문은 int j = i i; j < n으로 구성해서 isPrime 배열에서 false로 돌린다.

3. isPrime배열에서 true인 소수의 개수만 체크해서 출력하면 완료!

Java 코드

    boolean[] isPrime = new boolean[n];
    for (int i = 2; i < n; i++) {
      isPrime[i] = true;
    }

    for (int i = 2; i * i < n; i++) {
      if (isPrime[i]) {
        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;
  }