[백준/Java] #1929 소수 구하기 - 시간초과 문제 해결

 

 

문제

 

 

 

 

 

코드

 

처음 작성했던 코드는 판별할 숫자를 2부터 증가하는 정수의 배수일 경우 소수가 아닌 것으로 판단하는 단순한 코드였다.

소수 여부를 판별하는 것은 어렵지 않지만, 계속해서 시간초과가 뜨는 바람에 다른 방식을 생각해야 했다.

 

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] s = br.readLine().split(" ");
        int min = Integer.valueOf(s[0]);
        int max = Integer.valueOf(s[1]);

        for (int i = min; i <= max; i++) {
            if (i == 1) continue;
            if (isPrime(i)) bw.write(i + "\n");
        }
        bw.close();
    }

    static boolean isPrime(int i) {
        for (int j = 2; j <= Math.sqrt(i); j++) {
            if (i % j == 0)  return false;
        }
        return true;
    }
}

 

시간을 단축시키기 위해 `BufferedReader`와 `BufferedWriter`를 사용하였고,

2부터 판별할 숫자의 제곱근까지만 증가하는 정수의 배수일 경우 소수가 아닌 것으로 판별하도록 수정하였다.