Java - 소수 찾기

◎소수의 정의

소수는 자신보다 작은 1 이상의 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.

ex) 17은 17보다 작은 1이상의 두 개의 자연수를 곱하여 만들 수 없는 수이므로, 소수이다.

=> 즉, 1과 자신만을 약수로 갖는 수이다.

 

---

◎소수 판별 알고리즘 1

2부터 판별하는 수 전까지 나눠보고 나머지가 0이 안 나온다면 소수로 정의

public class Main {
    public static boolean isPrime(int num){ //num>3
        for(int i=2; i<num; i++){ //2~num-1까지 나눈다
            if(num % i == 0) return false;
        }
        return true;
    }
}

 

시간 복잡도: Olog(N)

---

◎소수 판별 알고리즘 2

소수 판별 알고리즘 1의 주요 골자는 2~num-1까지 중에 num의 약수가 있는지 판별하는 것이다.

그런데, (N>3인 자연수) N의 약수가 가질 수 있는 최솟값이 2이므로, N의 약수가 가질 수 있는 최댓값은 N/2이다.

그러므로, 2~N/2까지 중에 num의 약수가 있는지 판별하면 된다.

 

시간복잡도: Olog(N/2)

 

public class Main {
    public static boolean isPrime(int num){ //num>3
        for(int i=2; i<=num/2; i++){ //2~num/2까지 나눈다
            if(num % i == 0) return false;
        }
        return true;
    }
}

 

여기서 더 발전된 방법으로, (N>3인 자연수) N = sqrt(N)*sqrt(N)이므로, 곱해서 N이 되는 수(약수) 중에 하나는 sqrt(N)보다 크거나 같고 또 다른 하나는 sqrt(N)보다 작거나 같아야 한다.

그러므로, 2~sqrt(N)까지 중에 num의 약수가 있는지 판별하면 된다.

 

시간 복잡도: Olog(sqrt(N))

 

public class Main {
    public static boolean isPrime(int num){ //num>3
        for(int i=2; i*i<=num; i++){ //2~num/2까지 나눈다
            if(num % i == 0) return false;
        }
        return true;
    }
}

---

 

◎소수 판별 알고리즘 3 : 에라토스테네스의 체

1~N까지의 소수를 모두 구하여야 할 때 사용하는 알고리즘이다.

출처:위키백과-에라토스테네스의 체

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까지의 모든 소수를 구하고 싶다면, 소수 판별 알고리즘 2를 활용하여 (int)sqrt(120) +1 = 11까지의 배수만 지우면 남은 모든 수는 소수이다.

 

import java.util.*;

public class Main {
    public static ArrayList<Integer> isPrime(int num){ //num>3
        boolean[] SieveofEratosthenes = new boolean[num+1]; 
        SieveofEratosthenes[0] = true;
        SieveofEratosthenes[1] = true;
        
        //0,1은 소수가 아니므로 따로 처리
        ArrayList<Integer> total = new ArrayList<Integer>();
        for(int i=2; (i-1)*(i-1)<=num; i++){ 
            if(SieveofEratosthenes[i]==false){ //false인 수에 도달하면
                for(int p = 2; p*i<=num; p++ ){ //그 수의 배수 모두 true처리
                    SieveofEratosthenes[p*i]=true;
                }
            }
        }
        for(int i = 0; i<=num; i++){
            if(SieveofEratosthenes[i]==false){
                total.add(i);
            }
        }
        return total;
    }
    
    public static void main(String[] args) {
        ArrayList<Integer> total = isPrime(120);
        
        for(int i = 0; i< total.size(); i++){
            System.out.println(total.get(i));
        }
    }
}

---

※n의 증가에 따른 공간 복잡도

출처: https://choheeis.github.io/newblog//articles/2020-04/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%EC%B2%B4

n이 커지면 커질수록 극심한 차이를 보인다.