[백준] 4134 : 다음 소수 (Math.sqrt) - JAVA

백준 단계별 문제풀이 15단계 (약수, 배수와 소수2)

https://www.acmicpc.net/problem/4134

4134번: 다음 소수

 

 

# 문제

정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.

 

# 예제

입력

3
6
20
100

 

출력

7
23
101

 

 

# 필요개념

1초라는 시간 제한이 걸려있고, 정수의 크기가 크기 때문에 소수를 찾는 알고리즘을 효율적으로 짜야하는 문제였다. 소수인지 판단하는 방법은 크게 2가지를 생각했다.

 

 

1. 2부터 늘려가면서 나누어 나머지로 판단하기

반복문을 사용해서 하나하나 나눠서 나머지가 0이면 소수가 아닌 걸로 판단하는 방법이다. 처음에 이 방법으로 했다가 시간초과가 떴다. 어떻게 짜야할까 고민하다가 인수분해 과정을 생각해보았다.

 

예를 들어 36의 인수를 쓰면 다음과 같다.

1 2 3 4 6 9 12 18 36

 

인수를 가만히 보면 특징이 있다. 36의 제곱근인 6을 기준으로 대칭구조를 이룬다는 것! 36뿐만이 아니라 다른 수를 봐도 그렇다는 것을 알 수 있다.

 

25 => 1 5 25

 

반면 소수인 수들은 인수가 1과 자기자신이다. 그래서 내가 생각한 두번째 방법은 이것이다.

 

 

2. 2부터 대상의 제곱근까지만 나누어 나머지로 판단하기

1과 비슷하지만 비교해야 할 대상이 확실히 적어짐을 알 수 있다. 1번 방법의 시간복잡도가 O(n)이라면, 이 방법은 O(n^(1/2))가 됨을 알 수 있다!

이렇게 제곱근을 구할 수 있게 해주는 메소드가 있는데 바로 Math.sqrt()이다.

 

 

추가로 0과 1이 들어올 수 있기 때문에, 들어오는 수가 0이나 1이면 2로 바꾸어줬다. (예외처리)

 

 

# Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0 ; i < n ; i++) {
            long a = Long.parseLong(br.readLine());
            if (a <= 1) a = 2;
            int j = 0;
            while (true) {
                if (check(a + j)) {
                    sb.append(a + j).append("\n");
                    break;
                }
                j++;
            }
        }
        System.out.println(sb);
    }
    public static boolean check(Long a) {
        for (int j = 2 ; j <= Math.sqrt(a) ; j++) {
            if (a % j == 0) return false;
        }
        return true;
    }
}

 

# 결과