Computer ScienceAlgorithmProblem Solving

28. 소수 판별 문제(제곱근, 에라토스테네스의 체)

제곱근으로 판별

소수를 판별할 때, 굳이 모든 수를 검사 하지 않아도 된다.
주어진 수의 제곱근에 해당하는 수까지 검사하면 된다.

1
2
3
4
5
6
7
boolean isPrime(int num){
    if(num == 1) return false;
    for(int i = 2 ; i < Math.sqrt(num); i++){
        if(N%i == 0) return false;
    }
    return true;
}

에라토스테네스의 체

이건 제곱근과는 달리 값의 범위 안에서 소수를 찾는다.
배열에 원하는 수 만큼 담아서 2를 만나면 그 뒤 2의 배수는 다 소수가 아니고,
그 다음에 3을 만나면 소수처리하고 그 뒤 3의 배수는 다 소수가 아니고…
이런식으로 구하려는 범위의 제곱근까지만 검사하면된다!!!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static final int MAX = 100000;
boolean[] findPrime(){
    boolean isPrime = new boolean[MAX+1];
    for(int i = 2 ; i <= MAX; i++){
        isPrime[i] = true;
    }
    for(int i = 2 ; i <= Math.sqrt(MAX) ; i++){
        if(isPrime[j] == false) continue;
        for(int j = i * 2 ; j <= MAX ; j+=i){            
            isPrime[j] = false;
        }
    }
    return isPrime;
}

관련된 문제로 백준6588번 문제가 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;
import java.io.*;

public class Main {
    public static final int MAX = 1000000;
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    	
        boolean[] isPrime = new boolean[MAX+1];
        for(int i = 2; i <= MAX; i++) {
            isPrime[i] = true;
        }
        for(int i = 2; i <= MAX; i++) {
            if(isPrime[i] == false) continue;
            for(int j = i * 2; j <= MAX; j += i) {                
                isPrime[j] = false;
            }
        }
    	
        while(true) {
            int n = Integer.parseInt(bf.readLine());
            boolean ok = false;
            if(n == 0)
                break;
            for(int i = 2; i <= n/2; i++) {
                if(isPrime[i] && isPrime[n-i]) {
                    System.out.println(n + " = " + i + " + "+(n-i));
                    ok = true;
                    break;
                }
            }
            if(!ok)
                System.out.println("Goldbach's conjecture is wrong.");
        }
    }
}

이번 문제에서 제일 신기했던건 printf보다 println이 훨씬 빠르다는 것!!!!

Share