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

문제

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

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

 

 

알고리즘 설계

 

일단 에라토스테네스의 체 문제를 풀고 와가지고 본 이 문제는 딱 봤을때 쉬웠다 

그런데 정답률이 27퍼밖에 되지않았던 이유는 에라토스테네스의 체로 풀지않으면 시간초과가 나는 문제였다

이전에 풀었던 에라토스테네스의 체 문제는 규칙에 따라 수를 삭제 하고 몇번째 삭제한 수가 몇이냐는 걸 묻는 문제였고

이 문제는 규칙에 따라 수를 삭제하고 해당 범위내의 소수를 출력하라는 문제였다

 

1. 소수인걸 true 소수가 아닌걸 false라 취급

2. 0과1은 소수가 아니므로 false로 둔다

3. 2부터의 수는 일단 소수라고 가정하고 true로 둔다

4. 2부터의 수는 에라토스테네스의 체 알고리즘에 의해 소수 판별을 한다 

 

point 선택한 수가 소수라면 선택한 소수의 배수는 무조건 소수가 아니라는게 포인트다 

        또한 에라토스테네스의 체는 반드시 2부터 시작하여야지 소수가 아닌 수가 완전히 걸러지는 알고리즘이다

 

이 과정을 다 거치면 소수인 수의 배열은 true를 갖고 소수가 아닌수의 배열은 false를 갖는다

 

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 []number=new boolean[m+1];
        number[0]=false;
        number[1]=false;
        for(int i=2;i<=m;i++) {
            number[i] = true;
        }

        for(int i=2;i<=m;i++) { //2부터 m의 수중에 작은수부터 들어온다 이 자리에 들어오는 수는 무조건 소수이다
            if (number[i]) { //왜냐하면 에라토스테네스의 체 알고리즘에 의해 소수가 아닌 수는 밑의 과정에서 걸러진다
                for (int j = i+i; j <= m; j+=i){  //선택한 소수의 배수는 무조건 소수가 아니다
                    number[j]=false;
                }
            }
        }

        for(int i=n;i<=m;i++){
            if(number[i]){ //소수만 출력
                System.out.println(i);
            }
        }

    }
}