BOJ#4134 다음 소수

BOJ#4134 다음 소수

* 문제

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

* 풀이

이 문제는 2가지 버전으로 풀어 보았다.

Solution#1 (메모리 : 73836 KB, 시간 : 1308 MS)

입력값이 0<= n <= 4*10^9 으로 굉장히 큰 수이다.

BigInteger를 이용해보자.

BigInteger에는 소수를 구하는 함수가 제공된다.

boolean java.math.BigInteger.isProbablePrime(int certainty)

BigInteger java.math.BigInteger.nextProbablePrime()

isProbablePrime함수의 파라미터에 대해서는 아래 링크를 참조하자.

http://stackoverflow.com/questions/21740745/clarification-of-the-certainty-factor-in-isprobableprime

(간단히 설명하면 소수가 확실히 아닌 경우에는 false를 return,

소수가 맞을 확률이 1-(1/2)^certainty 이상인 경우 true를 return 한다.)

소스 또한 간단하다.

입력값 n을 BigInteger 객체로 받고,

n이 소수이면 출력,

소수가 아니면 nextProbablePrime() 함수를 실행한다.

public class Main { public static void main(String[] args) throws IOException { int T; BigInteger n; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); T = Integer.parseInt(br.readLine()); for (int t = 0; t < T; t++) { n = new BigInteger(br.readLine()); if (n.isProbablePrime(100)) { System.out.println(n); } else { System.out.println(n.nextProbablePrime()); } } } }

Solution#2 (메모리 : 18276 KB, 시간: 308 MS)

위 방법을 쓰지 않고 구현하고자 했을 때, 힘들었던 점은 역시 입력값의 범위였다.

배열 선언 시 일정 크기 이상은 선언할 수 없기 때문이다.

참고. Do Java arrays have a maximum size?

http://stackoverflow.com/questions/3038392/do-java-arrays-have-a-maximum-size

따라서 아래의 성질을 이용하여 선언해야 할 배열의 size를 줄여보았다.

"n이 소수인지 판별하려는 수 일때, n의 양의 제곱근 보다 작은 소수로 나누어 떨어지지 않으면 n은 소수이다."

n의 최대값이 4*10^9 이므로

4*10^9 이상의 수에 대해 소수임을 판별하려면 sqrt(4*10^9) = 63,245보다 작은 소수들이 필요하다.

또한 소수 정리에 따라 4*10^9 근처의 소수의 간격은 ln(4*10^9)이므로,

즉, 4*10^9이 소수가 아니라고 해도 4*10^9 + ln(4*10^9) 이내에는 소수가 존재한다.

따라서 배열의 사이즈를 넉넉잡아 63300으로 설정하였다.

그리고 에라스토테네스의 체 방법을 이용하여 63300 배열에 소수를 채웠다.

(에라스토테네스의 체 : http://stack07142.tistory.com/31)

public static void main(String[] args) throws IOException { final int ARR_SIZE = 63300; int[] primeNum = new int[ARR_SIZE]; int T; long n; boolean isPrime = false; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); for (int i = 0; i < ARR_SIZE; i++) { primeNum[i] = 1; } // 소수 배열 구하기 - 에라스토테네스의 체 // 1이면 소수이고, 0이면 소수가 아니다. primeNum[0] = 0; primeNum[1] = 0; for (int i = 2; i < ARR_SIZE; i++) { for (int j = 2; i * j < ARR_SIZE; j++) { primeNum[i * j] = 0; } } // 입력 받은 수 n에 대하여 n보다 크거나 같은 소수 중 가장 작은 소수를 구해보자. T = Integer.parseInt(br.readLine()); for (int t = 0; t < T; t++) { n = Long.parseLong(br.readLine()); if (n <= 1) { System.out.println(2); } else { for (long i = n;; i++) { int m = (int) Math.sqrt(i); isPrime = true; for (int j = 1; j <= m; j++) { if (primeNum[j] == 1) { if (i % j == 0) { isPrime = false; break; } } } if (isPrime) { System.out.println(i); break; } } } } }

잘못된 내용이 있는 경우

댓글로 지적/보완 부탁드립니다. 

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%234134_NextPrime