프로그래머스 - 소수찾기

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

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

제한 조건
n은 2이상 1000000이하의 자연수입니다.

---

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for (int i=2; i<=n; i++) {
            boolean isPrime = true;
            for (int j=2; j<=Math.sqrt(i); j++) {
                if (i%j == 0 ) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                answer++;
            }
        }
        
        return answer;
    }
}

• 2부터 자기 자신의 수까지 루프돌면서 소수를 찾는 방법은 O(n^2) 으로 시간초과 발생

• 제곱근까지만 확인해도 소수인지 확인할 수 있다.
  2부터 N의 제곱근까지 나눈다

• 에라토스테네스의 체
  2가 소수인 경우, 2의 배수를 모두 제거
  3이 소수인 경우, 3의 배수를 모두 제거
  이러한 방식으로 제곱근N까지 반복하여 나눠떨어지지않는 수 찾기

import java.util.*;
class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean[] isPrime = new boolean[n+1];
        
        for(int i=0; i<=n; i++) {
            if (i < 2) isPrime[i] = false;
            else isPrime[i] = true;
        }
        
        // 제곱근까지만 확인하여 불필요한 반복 줄인다
        for (int i=2; i<=Math.sqrt(n); i++) {
            // 소수 아님이 판별된 수는 패스
            if(!isPrime[i]) continue;
            
            // n이하 자연수 중 소수의 배수들은 제외
            for(int j=i*2; j<=n; j+=i) {
                isPrime[j] = false;
            }
        }
        System.out.println(Arrays.toString(isPrime));
        
        for (int i=0; i<isPrime.length; i++) {
            if(isPrime[i]) {
                answer++;
            }
        }
        
        return answer;
    }
}