[Java] 백준알고리즘 #4134 다음 소수

백준알고리즘 #4134 다음 소수

백준알고리즘 #4134 다음 소수

 

입력받은 n 보다 크거나 같은 소수 중 가장 작은 소수를 출력하는 문제.

 

입력받은수가 소수인지 판별하기 위해 1부터 n 혹은 n/2 까지 반복하며 약수를 확인하다보면 시간 초과 오류가 발생한다.

이는 문제에 나온 힌트처럼 루트n 까지만 나눠서 확인하면 시간 효율을 높일 수 있다.

 

왜 그런지 확인해보자.

 

예를 들어 어떤 수 N이 소수가 아닌 합성수라고 한다면,

N은 어떤 약수 a와 b를 이용해 a x b 로 나타낼 수 있다.

이 때, a가 b보다 크다고 하자.

그렇다면 "a x a 는 a x b 보다 크거나 같다" 라는 것을 알 수 있다.

 

한 예로 100인 경우, 10^2으로 나타낼 수 있고 100의 약수는 1,2,4,5,10,20,25,50이 있는데

2 x 50, 4 x 25, 5 x 20, 10 x 10 의 식을 만들 수 있다.

이 때 50, 25, 20 도 10보다 큰 약수이긴 하지만, 곱해지는 수가 2, 4, 5 가 되기 때문에

결국에는 소수 판별을 위해서는 해당 수의 제곱근까지의 수만 확인해보면 판별할 수 있게 되는 것이다.

 

전체 코드를 보면 다음과 같다.

 

// 해설참조 : sehyeok.tistory.com 

import java.util.Scanner;

public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        for (long i = 0; i < n; i++) {
            long a = sc.nextLong();
            while (true) {
                long count = 0;
                for (long j = 2; j <= Math.sqrt(a); j++) {
                    if (a % j == 0) {
                        count++;
                        break;
                    }
                }
                if (count == 0) {
                    if (a == 0 || a == 1) {
                        a = 2;
                    }
                    System.out.println(a);
                    break;
                }
                a++;
            }
        }

        sc.close();
    }
}

 

충분히 큰 수를 저장하기 위해 long변수를 이용해 수(a)를 입력받고,

1은 모든 수의 약수이므로 2부터 n의 제곱근(Math.sqrt() 함수 이용) 까지 반복하면서 나눠준다.

나머지가 0이라면 count변수를 증가시키고 이는 소수가 아니라는 뜻이므로 break를 이용해 루프를 빠져나온다.

반복문이 끝난 후 count가 0이라면 (n의 약수가 없다면) 이는 소수라는 의미이므로 a를 출력하면 완성.

다만 a가 0 혹은 1인 경우 소수에 포함되지 않으므로 (가장 작은 소수는 2이다) 이 경우에 한해 a에 2를 대입해준다.