프로그래머스 소수찾기

class Solution {
    public int solution(int n) {
        //보통 소수찾는 알고리즘에서는 에라토스네스체의 방식이 사용됨 소수 찾을 땐 이게 짱임
        int answer = eratosneSosu(n);

        return answer;
    }
    //에라토스네스체 구현 방법
    //2부터 n의 제곱근까지 돌면서 자신의 을 제외하고 자신의 배수들 다 지우기
    public int eratosneSosu(int n){
        int arr[] = new int[n+1];
        //일단 1부터 정해진 곳까지 전부 수를 채운 배열을 만듬
        for(int i=1; i<=n; i++){
            arr[i] = i;
        }
        //소수는 2부터 시작하므로 i=2
        //n의 제곱근까지 배열을 돌면 다 지워짐
        for(int i =2; i<=Math.sqrt(n); i++){
            //이미 지워졌다면 for문 넘기기
            if(arr[i] == 0){
                continue;
            }
            //지워지지 않았다면 i의 배수들 다지우기  
            //i*i부터 시작하는 이유는
            //i*1, i*2 ... 은 1*i 2*i 를 통해 이미 지워졌기 떄문이다.
            for(int j = i*i; j<=n; j+=i){
                arr[j] =0;
            }
        }
        int count = 0;
        for(int i=2; i<=n; i++){
            if(arr[i] != 0){
                count++;
            }
        }
        return count;
    }
}

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

코딩테스트 연습 - 소수 찾기