[JAVA] 알고리즘 : 배열 - 소수(에라토스테네스 체)

import java.util.*;

public class Main{
    public int solution(int n){
        int answer = 0;
        int[] ch=new int[n+1];

        for(int i=2; i<=n; i++){
            if(ch[i]==0){
                answer++;
                for(int j=i; j<=n; j=j+i){ // j는 i의 배수로 돌아야 함
                    ch[j]=1;
                }
            }
        }
        return answer;
    }
    public static void main(String[] args) {
        Main T=new Main();
        Scanner kb=new Scanner(System.in);
        int n = kb.nextInt();
        System.out.println(T.solution(n));
    }
}

 

입력받은 n의 크기인 배열을 만들어

이중 for문을 돌며 인덱스가 i의 배수인 원소들을 0에서 1로 바꾼다.

그리고 answer를 증가시킨다. 

예를 들어 i=2라고 하면 2, 4, 6, 8 ... 이런 2의 배수들은 소수가 아니므로 1로 바꾸는 것이다. 

그리고 i를 증가시켜 3이 되고 3은 소수이므로 answer++, 3의 배수들은 또 1로 바꾼다.

 

이런식으로 어떤 숫자의 배수가 아닌 것들만 찾아 개수를 구한다.