백준 1929번 - 소수 구하기 / Java

문제

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

1929번: 소수 구하기

M과 N사이의 소수를 구하는 문제.

단순하게 M부터 1씩 더 해가며 N까지 모든 경우의 수를 검사하는 방법은 시간이 부족해서 틀린다.

 

M과 N사이의 소수를 구하는 방법 중 가장 좋은 방법인 에라토스테네스의 체 를 사용하면 간단하게 구할 수 있는 문제

 

 

알고리즘

1. 가장작은 소수인 2부터 시작해서 소수의 배수를 모두 체크한다

2. 1씩 더 해가며 배수를 지우는데, 체크가 되어있는 수는 이미 소수가 아니므로 건너뛴다

3. 체크가 안되어있으면 소수이므로 리스트에 추가한다

 

소스코드 및 설명

 

1,2,3번 알고리즘

        for(int i=2;i<=n;i++) { //가장 작은 소수인 2부터 시작
            if(check[i]==false && i>=m) { // 배수가 아니고 i가 m보다 크다면(m과n사이의 소수니까)
                prime.add(i); // i는 소수니까 리스트에 추가
                for(int j=i*2;j<=n;j=j+i) { // 소수의 배수 모두 true로 체크 
                    check[j] = true;
                }
            }
        }

 

전체 소스코드

/*
 * BOJ1929
 * 2020.01.16
 * Hyeonseong
 */
import java.util.*;
public class BOJ1929 {
    public static void main(String[] args) {
        Solution s = new Solution();
    }
}
class Solution{
    public Solution() {
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        int n = scan.nextInt();
        
        boolean[] check = new boolean[10000001];
        ArrayList<Integer> prime = new ArrayList<Integer>(); //소수 리스트
        
        for(int i=2;i<=n;i++) { //가장 작은 소수인 2부터 시작
            if(check[i]==false && i>=m) { // 배수가 아니고 i가 m보다 크다면(m과n사이의 소수니까)
                prime.add(i); // i는 소수니까 리스트에 추가
                for(int j=i*2;j<=n;j=j+i) { // 소수의 배수 모두 true로 체크 
                    check[j] = true;
                }
            }
        }
        
        for(int i : prime) {
            System.out.println(i);
        }
    }
}