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

📎 문제 출처

---

https://school.programmers.co.kr/learn/courses/30/lessons/12921

📌 문제 설명

---

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

❓ 풀이 방법

---

에라토스테네스의 체를 사용해서 문제를 풀었다.
처음에는 for문의 범위를 n까지로 해서 런타임에러가 생겼다.
이를 해결하기 위해 n의 범위를 n의 제곱근으로 수정했다.
n이 소수가 아니라면, 그 수의 약수는 반드시 sqrt(n) 이하에 존재하기 때문이다.

📌 Code

---

import java.util.*;
class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean[] isPrime = new boolean[n+1];
        Arrays.fill(isPrime, true);
        
        isPrime[0] = isPrime[1] = false;
        
        for(int i = 2; i <= Math.sqrt(n); i++) {
            if(isPrime[i]) {
                for(int j = i * i ; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        for(int i = 2; i <= n ; i++) {
            if(isPrime[i]) answer++;
        }
        return answer;
    }
}