[JAVA] 에라토스테네스의 체

에라토스테네스의 체

■ 정의

소수를 찾는 방법 중 하나로, '소수가 되는 수의 배수를 지우면 남은 건 소수가 된다' 라는 알고리즘
소수가 무엇인지 찾을 필요가 없으며, 2부터 자기 자신을 제외한 배수가 되는 것을 지움

​ - 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97이 남는데,  이것이 100 이하의 소수이다.
 - 7까지 찾는 이유는 8, 9, 10은 2와 3의 배수이므로 이미 지워진 상태이고, √100 < 11이기 때문이다.

 

■ 사용 예 (백준 No.17103)

17103번: 골드바흐 파티션

 

■ Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static boolean isPrime(int num){
        if(num == 1)
            return false;
        for(int i = 2; i <= Math.sqrt(num); i++){
            if(num % i == 0)
                return false;
        }
        return true;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        for(int i = 0; i < T; i++){
            int N = Integer.parseInt(br.readLine());
            int count = 0;

            for(int j = 2; j <= N / 2; j++){
                if(isPrime(j) && isPrime(N - j))
                    count++;
            }
            System.out.println(count);
        }

    }
}

 - 처음 풀 때 에라토스테네스의 체를 사용하지 않았는데, 그럴 경우 시간초과 에러가 발생하였다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        boolean[] num = new boolean[1000001];
        num[0] = num[1] = true; // true = 소수 아님,  false = 소수
        for(int i = 2; i <= Math.sqrt(1000000); i++){
            if(!num[i]){
                for(int j = i * 2; j <= 1000000; j += i){
                    num[j] = true;
                }
            }
        }

        for(int i = 0; i < T; i++){
            int N = Integer.parseInt(br.readLine());
            int cnt = 0;

            for(int j = 2; j <= N / 2; j++){
                if(!num[j] && !num[N - j])
                    cnt++;
            }
            System.out.println(cnt);
        }
    }
}

 - 에라토스테네스의 체를 사용하면 시간초과가 발생하지 않았다.