[JAVA] ★ 소수 찾기 - 에라토스테네스의 체

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

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

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

풀이1 (효율성 테스트 실패) - 제곱근 보다 작은 자연수로 모두 구하기

class Solution {
    public int solution(int n) {
        int answer = 0;
        for(int i=1; i<=n; i++){
            int cnt = 0;
            for(int j=1; j*j<=i; j++){
                if(j*j==i) cnt++;
                if(i%j==0) cnt+=2;
            }
            if(cnt==2){
                answer++;
            }
        }
        return answer;
    }
}

풀이 - 에라토스테네스의 체

• 지워지지 않는 가장 작은 수를 찾음(보통 2부터 시작)
• 해당 수는 소수이다
• 해당 수의 배수들을 모두 지운다

class Solution {
    public int solution(int n) {
        int answer = 0;
        int[] arr = new int[n+1]; 
        // 2~n번까지 숫자 넣기 그 이외는 0으로 두기
        for(int i=2; i<=n; i++){
            arr[i] = i;
        }
        for(int i=2; i<=n; i++){
            // 이미 0이면 다음 숫자로
            if(arr[i]==0){
                continue;
            }
            // 지워지지 않은 숫자의 배수를 0으로 제외시키기
            for(int j=i+i; j<=n; j+=i){
                arr[j] = 0;
            }
        }
        
        // 0이 아닌 것이 소수
        for (int i = 2; i <= n; i++) { 
            if (arr[i] != 0) {
                answer++;
            }
        }
        return answer;
    }
}