백준 1929 - 소수 구하기

Java

1929 번 - 소수 구하기

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. (1 ≤ M ≤ N ≤ 1,000,000)

접근 방법

소수 구하는 문제이다.
n이라는 숫자가 있으면 2부터 n-1까지 탐색하여 n을 나눌 수 없으면 n은 소수이다.
하지만 위 방법은 시간초과를 초래하므로, n-1까지 대신 Root n 까지 반복하여 소수인지 판별한다.

코드

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

public class Main {
	static int n, m, result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	
    	StringBuilder sb = new StringBuilder();
    	boolean isPrime = true;
    	for(int i = n; i <= m; i++) {
    		if(i == 1)		// 1은 소수가 아니다
    			continue;
    		isPrime = true;
			// 2부터 root(i) 까지 수 중 나누어 떨어지지 않으면 소수이다.
    		for(int j = 2; j <= Math.sqrt(i); j++) {
    			if(i % j == 0) {
    				isPrime = false;
    				break;
    			}
    		}
    		if(isPrime)
    			sb.append(i).append("\n");
    	}
	}
}	

총평

후기

1은 소수가 아니다!!!!!

개선할 점

없습니다.