[프로그래머스] 소수 찾기

✨️ 문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

 -> 자세한 내용 보러가기

🎲 자바 풀이

import java.util.*;

class Solution {
    public int solution(int n) {
        if (n <= 1) return 0;

        int count = (n - 1) / 2; // 2를 제외한 홀수의 개수
        boolean[] primes = new boolean[count + 1];
        Arrays.fill(primes, true);

        for (int i = 3; i * i <= n; i += 2) {
            if (primes[i / 2]) {
                for (int j = i * i; j <= n; j += i * 2) {
                    primes[j / 2] = false;
                }
            }
        }

        int countPrimes = 1; // 2는 소수
        for (int i = 1; i <= count; i++) {
            if (primes[i]) countPrimes++;
        }

        return countPrimes;
    }
}

풀이 설명

1. 2를 제외한 모든 짝수는 소수가 아니기 때문에 홀수만을 대상으로 코드를 실행해야한다. 따라서 count 변수를 (n - 1) / n으로 초기화하였다.
2. primes 배열을 이용하여, 각 인덱스에 해당하는 숫자가 소수인지 여부를 표시하였다. 초기에는 모든 숫자를 소수로 가정하여 true로 초기화 하였다.
3. 3부터 시작하여, 홀수만을 대상으로 반복문을 수행한다. 현재 숫자가 소수라면 그 숫자의 배수는 소수에서 제외한다.
4. primes 배열에서 true로 남아있는 요소들의 개수를 세어 소수의 개수를 구한다.