백준 1929 : 소수 구하기 - 자바 문제 풀이(시간 초과 해결)

 

백준 1929 소수 구하기 문제입니다.

 

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

1929번: 소수 구하기

 

다음과 같이 시간초과가 뜨더군요 그래서 저는 자바에서 제공되는 Math 클래스의 sqrt인 제곱근을 활용하였습니다.

 

소수를 구하는 prime(int n) 메서드입니다.

저번에 블로그에 올렸던 코드와 유사하지만 Math.sqrt(n)으로 반복문의 반복을 줄였습니다. 

 

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

전체 코드입니다.

Scanner가 아닌 버퍼드리더를 사용하여 시간을 줄였습니다.

import java.io.*;
import java.math.*;

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 a = Integer.parseInt(s[0]);
		int b = Integer.parseInt(s[1]);
		for (int i = a; i <= b; i++) {
			if (i == 1)
				continue;
			if (prime(i)) {
				bw.write(i + "\n");
			}
		}
		bw.flush();
		bw.close();

	}

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