에라토스테네스의 체 (소수판별)

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

소수 판별은 에라토스테네스의 체보다 빠른 방법이 없다.

1) 2부터 N까지 모든 정수를 적는다.

2) 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.

3) P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.

4) 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

1을 지우고(1은 소수 아님)

2를 제외한 2의 배수를 지우고

3을 제외한 3의 배수를 지우고

4는 이미 지웠으니 x

5를 제외한 5의 배수를 지우고

7을 제외한 7의 배수를 지우면 된다.
(1~100사이의 소수를 구한다면 여기까지)

1~100까지의 소수

다만 에라토스테네스의 체는 '특정 범위 내의 소수'를 판정하는 데에만 효율적이다. 만약 주어진 수 하나가 소수인가? 만을 따지는 상황이라면 이는 소수판정법이라 해서 에라토스테네스의 체 따위와는 비교도 안되게 빠른방법이 넘쳐난다.

출처 : https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

class Solution {
    public int solution(int n) {
        int answer = 0;       
        int [] arr = new int[1000001];
		
        //에라토스테네스의 체를 하기위해 2~n까지 저장
		for(int i=2;i<=n;i++) arr[i] = i;	     
        
        //2~n까지 지우지 않은 값은 소수
		for(int i=2;i<=n;i++) {
			if(arr[i] != 0) {
				answer++;
                
                //지우지 않은 값의 배수들을 지워줘서 소수가 아님을 판단.
				for(int j=1;i*j<=n;j++) arr[i*j]=0;	
			}
		}
        
        return answer;
    }
}