백준 / 1929 소수구하기 (수정필요)

1378 단어 백준소수백준

문제


풀이

M이상 N이하의 소수를 모두 출력하는 문제이다.
다음의 문제를 풀기 위해서 쓰는 방법은 주로 '에라토스테네스의 체'이다.

'에라토스테네스의 체'에 대한 설명은 다음 링크의 설명을 참고하자
https://velog.io/@dogit/%EB%B0%B1%EC%A4%80-2581-%EC%86%8C%EC%88%98

코드

import java.util.*;

public class Main {
    public static void main(String args[]) {
    
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        //에라토스테네스의 체 알고리즘
        boolean[] check = new boolean[m+1];
        check[0] = check[1] = true;
        
        for (int i=2; i*i <= m; i++) {
            if (check[i] == true) {
                continue;
            }
            for (int j=i+i; j<=m; j+=i) {
                check[j] = true;
            }
        }
        
        for (int i=n; i<=m; i++) {
        	// false = 소수 
            if (check[i] == false) {
                System.out.println(i);
            }
        }
    }
}

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

좋은 웹페이지 즐겨찾기