*에라토스테네스의 체* chebyshevtheo

수학에서 에라토스테네스의 체는 소수를 찾는 방법이 다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.

2. 2는 소수이므로 자기 자신을 제외한 모든 배수를 지운다.

3. 남아있는 수 중에 가장 작은 수인 소수 3을 제외하고 다시 3의 모든 배수를 지운다.

4. 다음은 남아있는 소수 5를 제외하고 5의 배수를 모두 지운다.

5. 이것을 반복한다.

 

핵심

위 문제를 풀기 위해 앞서 살펴본 에라토스테네스의 체 알고리즘을 사용한다.

 

정답 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int max = 1000000;
        boolean[] arr = new boolean[max+1];
        Arrays.fill(arr,true);

        for (int i=2; i<=max; i++){
            for (int j=i*2; j<=max; j+=i){
                arr[j] = false;
            }
        }

        while (true){
            int n = sc.nextInt();
            if (n==0) break;

            int count =0;
            for (int i=n+1; i<=2*n;i++){
                if (i==1)continue;
                if (arr[i])count++;
            }
            System.out.println(count);
        }


    }
}

 

해설

넉넉하게 배열의 크기를 1000000으로 잡는다.

그리고 boolean타입의 배열 안에 모든 값을 true로 변경해준다.

앞서 살펴본 에라토스테네스의 체 알고리즘을 사용하여,

2부터 시작하여 자기 자신을 제외한 배수를 모두 false로 바꾼다.

입력받은 수를 기준으로 n~2*n사이에서

true(소수)의 개수를 찾아서 반환해준다.

 

 

 

 

개선점이나 오류가 있다면 , 댓글 부탁드립니다.