[알고리즘 개념] 소수 구하기, 소수 판별 / JAVA

소수(Prime Number)란

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

알고리즘 문제중에 소수판별 및 구하는 문제는 많이 나온다.

 

개발자들 사이에서 소수를 중요시 여기는 이유는 암호화방식에 소수를 많이 쓰기 때문입니다.

대표적으로 RSA암호방식이 있습니다.

2022.01.27 - [CS/NetWork] - [네트워크] 대칭키(Symmetric key), 공개키(Public Key), RSA 암호화

 

 

3가지방식으로 구해볼 예정

 

방법1(N미만 수로 나누기)

위에서 얘기했듯 1과 본인의 수(N)로만 나눠져야하므로,

1과 N를 제외한 약수가 있다면 소수가 아님.

N미만의 수로 나누어서 확인

 

시간복잡도

해당숫자만 소수판별: O(N)
숫자이하 소수구하기: O(N^2)

import java.util.Scanner;

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

        int num = sc.nextInt();


        // 해당 숫자 소수 판별만 할때
        if(solve(num)){
            System.out.println("소수");
        }else{
            System.out.println("소수 아님");
        }

        // 해당 숫자이하에 모든 소수를 구할때
        for(int i = 0; i <= num; i++){
            if(solve(i)){
                System.out.printf("%d는 소수\n",i);
            }else{
                System.out.printf("%d는 소수 아님\n",i);
            }
        }
    }

    public static boolean solve(int num){

        // 0 또는 1은 소수가 아님
        if(num < 2) return false;
        

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

        // 그외의 수
        for(int i = 2; i < num; i++){

            //num보다 아래수에서 나눠지는 수가 있으면 소수가 아님
            if(num % i == 0){
                return false;
            }
        }

        //안나왔으면 소수
        return true;
    }
}

 

방법2(루트 N 이하 수 나누기)

위의 방식에서 루트를 사용하는 방식.

루트를 사용해도 되는 이유.

 

입력 숫자 16

 

1 * 16

2 * 8

4 * 4

8 * 2

16 * 1 

 

둘중에 하나는 N에 루트를 씌운것보다 같거나 작다.

즉 받은 숫자 N을 루트씌우고 그 이하의 숫자들로만 나눠보면 됨.

 

시간복잡도

해당숫자만 소수판별: O(√N)
숫자이하 소수구하기: O(N√N)

import java.util.Scanner;

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

        int num = sc.nextInt();


        // 해당 숫자 소수 판별만 할때
        if(solve(num)){
            System.out.println("소수");
        }else{
            System.out.println("소수 아님");
        }

        // 해당 숫자이하에 모든 소수를 구할때
        for(int i = 0; i <= num; i++){
            if(solve(i)){
                System.out.printf("%d는 소수\n",i);
            }else{
                System.out.printf("%d는 소수 아님\n",i);
            }
        }
    }

    public static boolean solve(int num){

        // 0 또는 1은 소수가 아님
        if(num < 2) return false;
        

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

        // 그외의 수(루트이하의 수로 나눠보기)
        for(int i = 2; i <= Math.sqrt(num); i++){

            //루트이하 수에서 나눠지는 수가 있으면 소수가 아님
            if(num % i == 0){
                return false;
            }
        }

        //안나왔으면 소수
        return true;
    }
}

 

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

에라토스테네스의 체 이용 방식.

 

K = 2부터 루트N 이하까지 반복하며, 자연수들 중 K를 제외한 K의 배수 제외

 

 

즉 위에서처럼 루트만큼 확인.

확인할 숫자의 배수는 다 소수가 아니므로 체크해두기.

이 과정을 다 거치면 남은 것들이 소수임.

 

시간복잡도

해당숫자만 소수판별,숫자이하 소수구하기: O(Nlog(log N))

import java.util.Scanner;

public class Test {

    public static boolean[] prime; // 소수판별 저장 배열
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);

        int num = sc.nextInt();

        solve(num);
        // 해당 숫자이하에 모든 소수를 구할때
        for(int i = 0; i <= num; i++){
            if(prime[i] == false){
                System.out.printf("%d는 소수\n",i);
            }else{
                System.out.printf("%d는 소수아님\n",i);
            }
        }
    }

    public static void solve(int num){
        // 0~num까지 true면 소수가 아님
        prime = new boolean[num+1];
        
        // 들어온 수가 2이하라면 바로 탈출
        if(num < 2) return;
        
        // 0과 1은 소수가 아닌걸로 처리
        prime[0] = prime[1] = true;


        // 그외의 수(루트이하의 수로 나눠보기)
        for(int i = 2; i <= Math.sqrt(num); i++){

            // 이미 확인된거면 패스
            if(prime[i] == true){
                continue;
            }

            // 배수부터 시작하여 다음배수만큼 증가
            for(int j = i*i; j < prime.length; j = j+i){
                // 소수아닌걸로 처리
                prime[j] = true;
            }
            
        }
    }
}

 

 

---

참조

https://st-lab.tistory.com/81

JAVA [자바] - 소수 구하는 알고리즘 및 구현