알고리즘 풀이/백준

[백준][Java] 1929번 소수 구하기

배게 2018. 4. 30. 01:42
728x90

에라토스테네스의 체가 뭔지 알면 쉽습니다


먼저 공부부터 하고

소수 구하기를 구현하시면 됩니다.



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int start = sc.nextInt();
		int end = sc.nextInt();
		
		boolean[] res = new boolean[end+1];
		for(int i=2; i<=end; i++) res[i]=true;
		
		for(int i=2; i<Math.sqrt(end); i++) {
			if(res[i]) {
				for(int j=2 ; i*j<=end ;j++ ) {
					res[i*j]=false;
				}
			}
		}
		
		for(int i=start;i<=end;i++) {
			if(res[i]) System.out.println(i);
		}
		
	}
}