문제

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

설명

주어진 N의 최대 값이 1000000이므로 이중 포문을 사용할 경우 제한 시간이 훌쩍 넘어 가버릴거다.
주인장은 에라토스테네스 체의 원리를 이용하여 이 문제를 풀어보았다.

에라토스테네스의 체

에라토스테네스 체는 각 수의 배수를 지워가며 소수를 찾아내는 알고리즘이다.

1. 구하고자 하는 소수의 범위 만큼 1차원 배열을 생성한다.
2. 2부터 시작하여 현재 숫자가 지워지지 않을 때 해당 숫자의 배수에 해당 하는 수를 배열에서 끝까지 탐색하며 지원다. 이때 처음으로 선택된 숫자는 지우지 않는다.
3. 배열의 끝까지 2번을 반복한 후 남아 있는 수를 모두 출력한다.

📖읽어보기 https://velog.io/@cod0216/알고리즘에라토스테네스의-체정수론

풀이 방법

1. 크기가 N+1인 배열을 선언한 후 초기화 해준다.
   

2. 1은 소수가 아니므로 0을 넣어주거나 삭제 한다.
   

3. 2부터 N의 제곱근까지 값을 탐색한다.
   

💡 N의 제곱까지만 탐색하는 이유!
N이 A*B라고 가정했을 떄, A와 B는 모두 N의 제곱근 보다 클 수 없다.

따라서 N의 제곱근까지만 확인해도 전체 범위의 소수를 판별할 수 있다

4. 해당 인덱스 값이 0이면 continue를 하며 스킵하고 0이 아니면 인덱스 값의 배수에 해당하는 배열의 값을 0으로 바꿔준다.
   
   

5. 배열에서 0이 아닌 수를 모두 출력한다.
   

코드

import java.io.*;
import java.util.*;
import java.lang.*;
public class J1929 {
    public static void main(String[] args) throws IOException{
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int m = scanner.nextInt();

        int[] numArray = new int[m + 1];

        for(int i = 0 ; i <= m; i++){
            numArray[i] = i;
        }
        numArray[1] = 0;


        for(int i = 2; i <= Math.sqrt(m); i++){
            if(numArray[i] == 0){
                continue;
            }
            for(int j = i+i; j<=m; j=j+i){
                numArray[j] = 0;
            }
        }

        for(int i = n; i <= m; i++){
            if(numArray[i] != 0)
            System.out.println(numArray[i]);
        }
    }
}