[Java] 소수 구하는 알고리즘

소수(Prime Number)

: 1보다 큰 자연수 중 1과 자기 자신만을 약수로 갖는 자연수

 

방법 1) " N 이하의 자연수들로 모두 나눠본다 . "

임의의 수 N이 1과 N을 제외한 다른 수를 약수로 갖고 있다면 그 수는 소수가 아니고, 만약 약수가 없다면 소수이다.

static boolean is_prime(int n) {
    // 0과 1은 소수가 아님
    if(n < 2)
        return false;

    // 2는 소수
    if(n == 2)
        return true;

    for(int i=2; i<n; i++)
        if(n % i == 0)
            return false;

    return true;
}

위 방법의 시간 복잡도는 O(N)

 

방법 2) " √N 이하의 자연수들로 모두 나눠본다. "

임의의 자연수 N이 p X q = N 을 만족 할 때, 예를 들어 N = 16 이면

 

1 X 16

2 X 8

4 X 4

8 X 2

16 X 1

 

위와 같이 p가 증가하면 q 가 감소하고, 반대의 경우도 동일하다.

결국 N을 임의의 수로 나누게 되면 임의의 수가 √N 보다 작다면 결국 나머지는 √N 보다 클 수 밖에 없다.

 

결과적으로 p와 q 중 하나는 반드시 √N 보다 작거나 같다.

static boolean is_prime2(int n) {
	// 0과 1은 소수가 아님
    if(n < 2)
        return false;

	// 2는 소수
    if(n == 2)
        return true;

    for(int i=2; i<= Math.sqrt(n); i++) {
        if(n%i == 0)
            return false;
    }

    return true;
}

위 방법의 시간 복잡도는 O(√N)

 

방법 3) 에라토스테네스의 체

" k=2 부터 √N 이하까지 반복하여 자연수들 중 k를 제외한 k의 배수들을 제외시킨다 "

k = 2 이면 2를 제외한 2의 배수를 모두 지우고,

k = 3 이면 3을 제외한 3의 배수를 모두 지우고,

(4는 k=2에서 이미 다 지워짐)

k = 5 이면 5를 제외한 5의 배수를 모두 지우고,

...

k=√N 까지 반복

 

 

 

 

 

 

public class Main {

	public static boolean[] prime;
	
	static void make_prime(int n) {
    	    // 0 ~ N
            prime = new boolean[n+1];

            /*
            소수가 아닌 index = true
            소수 index = false
            */

            prime[0] = prime[1] = true;

            for(int i=2; i<Math.sqrt(n); i++) {
                if(prime[i] == true)
                    continue;

                // i 의 배수들을 걸러주기 위함 (2,4,6... 등)
                for(int j=i*i; j<prime.length; j=j+i)
                    prime[j] = true;
	    }
        }
}

위 방법의 시간 복잡도는 O(Nlog(log N))

 

결론

대부분 소수 문제는 에라토스테네스의 체 쓰면 거의다 해결됨 !