백준 알고리즘 1929: 소수 구하기

일반적인 소수 구하는 방식을 사용했다가는 시간 초과가 뜬다. 시간복잡도가 O(n^2)이기 때문이다.

그렇기 때문에 다른방식으로 사용해서 문제를 풀었다.

또한 Scanner가 아닌 Buffer로 입출력을 받았느데 아직은 익숙치 않아서 불편하더라

그래도 시간면에서는 훨씬 효율적이라고 하니 익혀둬야겠다

import java.io.*;
import java.util.StringTokenizer;

public class Sol_1929 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        for(int i=m; i<=n; i++)
        {
            int div = 2;
            double root = Math.sqrt(i);
            boolean isPrime = true;

            if(i==1)
                isPrime = false;
            while(div <=root)
            {
                if(i % div == 0) {
                    isPrime = false;
                    break;
                }
                div++;
            }
            if(isPrime)
            {
                bw.write(String.valueOf(i));
                bw.newLine();
            }
        }
        bw.flush();
    }
}