[백준/Java] 1929번 소수 구하기 (에라토스테네스의 체)

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

1929번: 소수 구하기

 

 

 

 

for (N의 제곱근까지 반복하기)

{

     소수가 아니면 넘어감

     for (소수의 배수 값을 N까지 반복하기)

     {

          이 수가 소수가 아니라는 것을 표시하기

           ( 0으로 값을 변경 )

     }

}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

// 에라토스테네스의 체
// 소수 구하기
public class Main {
	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		// M 이상 N 이하의 자연수
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());

		// 배열
		int size = N + 1; // 큰 수보다 1 크게, 인덱스 1부터 시작하므로
		int[] A = new int[size];

		// 배열 초기화하기
		for (int i = 2; i <= N; i++) 
		{
			A[i] = i;
		}

		// 에라토스테네스의 체
		// 1은 소수가 아니므로 2부터 시작해서 마지막 수의 제곱근까지
		for (int i = 2; i <= Math.sqrt(N); i++) 
		{
			if (A[i] == 0) // 지워진 수이면
			{
				continue;
			}

			// 배수 지우기
			for (int k = i + i; k <= N; k = k + i)
			{
				A[k] = 0;
			}
		}
		
		// 소수 출력하기
		for (int i = M; i <= N; i++) 
		{
			if(A[i] != 0)
			{
				System.out.println(A[i]);
			}
		}

		br.close();
	}
}