[백준] 2581 - 소수 (Java)

---

 

에라토스테네스의 체

에라토스테네스가 발견한 소수를 찾는 방법! 

 

위키백과 사랑해요

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 위에서는 2~120 구간에서 소수를 구하니까 120의 제곱근인 약 10.95, 즉 10까지만 체크하면 나머지 수들은 자동으로 소수가 된다.

왜냐? 그전에 이미 구해진 약수들이 나머지 숫자들 중에 소수가 아닌 수들의 약수가 되기 때문이지!

 

 

 

https://st-lab.tistory.com/83?category=844846 

[백준] 2581번 : 소수 - JAVA [자바]

아래 코드는 위에서 확인 가능합니다.

 

 

 

// 에라토스테네스 체 알고리즘 
public static void get_prime() {
    prime[0] = true;
    prime[1] = true;

    for(int i = 2; i <= Math.sqrt(prime.length); i++) {
        if(prime[i]) continue;	// 이미 체크된 배열일 경우 skip
        for(int j = i * i; j < prime.length; j += i) {
            prime[j] = true;
        }
    }

}

0과 1은 소수가 아니니까 true 처리를 해주고 2부터 2의 배수 처리, 그 다음 3의 배수 처리, 다음, 다음 ... 소수가 아닌 숫자들을 빼준다.

 

public class Main {
 
    public static boolean prime[];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());

        prime = new boolean[N + 1];	
        get_prime();


        int sum = 0;
        int min = Integer.MAX_VALUE;
        for(int i = M; i <= N; i++) {
            if(prime[i] == false) { 
                sum += i;
                if(min == Integer.MAX_VALUE) {
                    min = i;
                }
            }
        }

        if(sum == 0) {
            System.out.println(-1);
        }
        else {
            System.out.println(sum);
            System.out.println(min);
        }

    }
 	...
}