[JAVA] 백준 1929번- 소수 구하기

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

1929번: 소수 구하기

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        while (n <= m) {
            if (isPrime(n)) {
                System.out.println(n);
            }
            n++;
        }
    }

    public static boolean isPrime(int n) {
        if(n==1) return false;

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

 

 

쉬운 문제도 정답률이 낮은 이유는 아마 시간초과 때문일것이다.

이전 소수 관련 문제들과 다름없이 isPrime함수에서 i를 n까지 돌렸더니 이 문제에서는 시간초과가 났다. 

사실 i를 n까지의 숫자로 다 나눠 검사할 필요는 없고 n의 제곱근까지만 나눠떨어지는지 확인하면 된다.

시간 복잡도가  O(√N) 으로 더 효율적이다.