소수하기

이번 포스팅 문제는 1929번 문제입니다.


문제요약

에라토스테네스의 체 알고리즘을 이용하여 자연수 M이상 N이하의 소수를 출력하는 문제입니다.

풀이전략



구현하기

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
28
29
30
31
32
33
34
35
36
package BackJoon.수학;
 
import java.util.Scanner;
 
/**
 * https://www.acmicpc.net/problem/1929
 * 에라토스테네스의 체
 * @author troh
 */
public class _1929_소수구하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int num1 = sc.nextInt();
        int num2 = sc.nextInt();
        
        boolean[] check = new boolean[num2+1];
        for(int i=2; i<=num2; i++) {
            if(!check[i]) {
                for(int j=i+i; j<=num2; j=j+i) {
                    check[j] = true;
                }
            }
        }
        
        int count = 0;
        for(int i=num1; i<=num2; i++) {
            if(i == 1continue;
            
            if(!check[i]) {
                System.out.println(i);
            }
        }
    }
}
 
cs

배운점

에라토스테네스의 체

+ Recent posts