소수 판정

방법 1. N 보다 작은 자연수들로 모두 나눠본다.

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

 

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

위 알고리즘은 N을 argument로 받아 N이하의 수까지 모든 수를 for문으로 돌기 때문에 시간 복잡도는 O(n).

위 알고리즘을 통해서 N 이하의 모든 소수를 구하는 알고리즘은 다음과 같다.

import java.util.Scanner;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        for (int i = 0; i <= N; i++) {
            if (isPrime(i)) System.out.println(i);
        }
    }
}

위 방법 1의 알고리즘을 for문을 N까지 한 번  더 돌기 때문에 시간복잡도는 O(N²)

 

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

 

* 왜 √N이하의 자연수들로 나누는 걸까?

N은 1과 자기 자신인 N를 제외한 다른 자연수를 약수로 가지면 안된다. 

p x q  = N ( 1 ≤  𝑝 , 𝑞 ≤ 𝐍 ) 으로 N을 표현 할 때,

p와 q중 하나는 반드시 √N 보다 작거나 같다.

p가 증가하면 q는 감소하는, 대칭적인 관계이기 때문에, √N이하의 범위만 확인하여 N에 나눠 떨어지는지 확인 후 소수판정을 하면 되는 것이다.

따라서 위의 코드를 아래와 같이 변경 할 수 있다.

public class PrimeNumber3 {
    public 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) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        for (int i = 0; i <= N; i++) {
            if (isPrime(i)) System.out.println(i);
        }

    }
}

바뀐점은 for문을 도는 범위만 감소 시켜 준 것이다.

따라서 시간복잡도는 O(N√N)이 되어 더 효율적인 코드가 된다.

 

방법 3. 에라토스테네스의 채

k=2 부터 √N 이하까지 반복하여 자연수들 중 k를 제외한 k의 배수들을 소수에서 제외시키는 것이다.

https://ko.wikipedia.org/wiki/에라토스테네스의_체

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

import java.util.ArrayList;
import java.util.Scanner;

public class PrimeNumber4 {
    public static void main(String[] args) {

        ArrayList<Boolean> primeList;

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n <=1 ) return;

        primeList = new ArrayList<>(n+1);
        // 0,1 소수 아님으로 처리
        primeList.add(false);
        primeList.add(false);
        // 2~n까지 소수로 일단 설정
        for (int i = 2; i <= n ; i++) {
            primeList.add(i,true);
        }
        // 2부터 i*i <=n 까지 각배수들 지워 나간다.
        for (int i = 2; (i*i) <= n; i++) {
            if (primeList.get(i)){
                // i제곱부터 i배수를 지워 나간다. 
                for (int j = i*i; j <= n ; j+=i) {
                    primeList.set(j,false);
                }
            }
        }

        for (int i = 0; i <=n ; i++) {
            if (primeList.get(i)){
                System.out.println(i);
            }
        }
    }
}

일단 ArrayList를 인덱스가 0부터 N까지 있도록 N+1의 배열을 생성한다.

0과 1은 False로 채우고, 2부터는 모두 True로 설정한 다음에,

2부터 1씩 증가하며 i*i <=N 까지 배수들을 지워 나간다.

 

그런데 왜 i 제곱 부터 지워 나갈까?

방법 2와 동일한 원리 이다.  i 보다 작은 수는 이미 2부터 시작해 지워져 있으므로 i 제곱 부터 i를 더해가며 소수를 지워 나가는 것이고, 동일하게 i 제곱 보다 N이 작거나 같은 범위에서만 배수를 지워주면 되는 것이다.

 

위의 시간복잡도는 그럼 어떻게 될까?

이중 for문을 돌고 있으므로 O(N²)일것 같지만 그렇지 않다.

O(Nlog(log N))의 시간 복잡도를 가진다.

 

N이하의 소수를 모두 출력하는 프로그램에서

방법 1은 O(N²)

방법 2는 O(N√N)

방법 3은 O(Nlog(log N))으로

시간복잡도가 점점 효율적으로 변하는 것을 확인 할 수 있다.

 

Reference 

https://st-lab.tistory.com/81?category=830901