[백준] 1929번 소수 구하기(JAVA)

문제

- 주어진 숫자 M이상 N이하의 소수를 모두 출력

- 1<=M<=N<=1,000,000

- M이상 N이하의 소수가 하나 이상 있는 입력만 주어짐

 

고찰

처음에는 주어진 범위의 숫자들에 대해서 각각을 2부터 해당 숫자까지 모든 숫자들로 나누어보면서 소수를 판별하는 알고리즘을 작성하였다.

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
		
        // M이상 N이하의 수 소수 판별
        for(int i = M; i<=N; i++){
            if(checkPrime(i)){
            	// 소수라면 출력
                sb.append(i).append("\n");
            }
        }

        System.out.println(sb);
        br.close();
    }
	
    // 소수 판별 알고리즘
    public static boolean checkPrime(int num){
        if(num<=1) return false;		// 1은 소수 아님
        else if(num==2) return true;		// 2는 소수
        else{					// 2부터 해당 숫자까지 차례로 나누어 봄
            for(int i = 2; i<num; i++){
                if((num % i) == 0) return false;
            }
            return true;
        }
    }
}

이 코드는 O(N) 알고리즘을 N-M번 반복하므로 O(N(N-M))의 시간복잡도를 가진다. 거의 O(N^2)와 같은 시간복잡도를 가지기 때문에 많은 시간이 소요되고 해당 코드를 제출하면 틀렸습니다.를 볼 수 있다.. 

 

그래서 √num 이하의 자연수들로만 num을 나누는 방법을 생각해보았다.

 

소수를 판별한다는 것은 1과 자기 자신을 제외한 다른 자연수를 약수로 가지고 있으면 안된다는 의미이다.

 

임의의 자연수 N이 있을 때, p x q = N을 만족하면 p와 q는 N의 약수라고 할 수 있다.

예를 들어 N = 8이면, 1 x 8, 2 x 4, 4 x 2, 8 x 1과 같이 두 수의 곱으로 표현할 수 있다. 이처럼 p가 증가하면 자연스레 q가 감소하고, p가 감소하면 자연스레 q가 증가한다.

p와 q 중 하나는 반드시 √N보다 작거나 같은 것을 확인할 수 있다. 즉,  √N 이하의 자연수 중에 나누어 떨어지는 수가 있다면 1과 N을 제외한 다른 자연수가 N의 약수라는 의미이므로 소수가 아니다.

 

코드

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        
        // M이상 N이하의 수 소수 판별
        for(int i = M; i<=N; i++){
            if(checkPrime(i)){
            	// 소수라면 출력
                sb.append(i).append("\n");
            }
        }

        System.out.println(sb);
        br.close();
    }

    // 소수 판별 알고리즘
    public static boolean checkPrime(int num){
        if(num<=1) return false;		// 1은 소수 아님
        else if(num==2) return true;		// 2는 소수
        else{					// 2부터 sqrt(num)까지 차례로 나누어 봄
            for(int i = 2; i<=Math.sqrt(num); i++){
                if((num % i) == 0) return false;
            }
            return true;
        }
    }
}