개발자 미니민의 개발스터디

[백준 JAVA] 4134번 풀이 - 다음 소수

by mini_min

계속 틀리네... 시간초과.....

package quiz;

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

/**
 * 다음 소수
 * 정수 n이 주어졌을 때, n보다 크거나 같은 소수 중에 가장 작은 소수를 찾는 프로그램을 작성하시오.
 * @author Back
 */
public class _ {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int testCaseCount = Integer.parseInt(br.readLine());

        for ( int i = 0; i < testCaseCount; i++ ) {
            long testCase = Long.parseLong(br.readLine());
            test(testCase);
        }

    }

    private static long test(long testCase) {

        while(true) {
            ++testCase; //7
            if ( getSosu(testCase) ) {
                System.out.println(testCase);
                break;
            }
        }

        return testCase;
    }

    private static boolean getSosu(long num) {
        boolean sosu = true;
        long b = 2;
        while( b < num ) {
            if ( num % b == 0 ) {
                sosu = false;
                break;
            }
            b++;
        }
        return sosu;
    }
}

 

풀이

시간 초과 열 받는다...!!ㅠㅠㅠㅠ

소수 열심히 구했는데... 답은 잘 나오는데.. 1과 본인 이외의 수로 나머지가 0이 아닌 애가 소수이도록 구했는데 ㅠㅠ... 시간 초과 어찌합니까...!

어쩔 수 없다... 공부할 겸 isPrime 을 사용하는 수 밖에 ! 

 

다시 푼 답안

package quiz;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Scanner;

/**
 * 다음 소수
 * 정수 n이 주어졌을 때, n보다 크거나 같은 소수 중에 가장 작은 소수를 찾는 프로그램을 작성하시오.
 * @author Back
 */
public class _ {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int testCaseCount = Integer.parseInt(br.readLine());

        for ( int i = 0; i < testCaseCount; i++ ) {
            long testCase = Long.parseLong(br.readLine());

            BigInteger primeNumber = new BigInteger(String.valueOf(testCase));

            if (primeNumber.isProbablePrime(10)){
                System.out.println(primeNumber);
            } else {
                System.out.println(primeNumber.nextProbablePrime());
            }
        }

    }

}

 

 

블로그의 정보

개발자 미니민의 개발로그

mini_min

활동하기