#1929 : 소수 구하기

풀이방법

사용된 것:

수학

에라토스테네스의 체

 

2022.06.19

에라토스테네스의 체를 사용하여 1부터 1,000,000 사이의 모든 소수를 구해놓는다.

구해놓은 데이터를 바탕으로 정답을 출력하면 된다.

 

코드

Java(2022.06.19)

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner (System.in);
		
		int start = sc.nextInt();
		int end = sc.nextInt();
		
		//에라토스테네스의 체 수행
		boolean[] arr = new boolean[1000001];	//i가 소수이면 arr[i]가 true인 배열
		Arrays.fill(arr, true);
		arr[0] = false;	//0은 소수가 아님
		arr[1] = false;	//1은 소수가 아님
		for(int i=2; i<1000001; i++) {	//2부터 1000000까지의 정수에 대하여
			if(arr[i]) {	//소수인 정수 i가 발견되면
				int mul = i*2;	//i의 2배수 이상부터 시작해여 모든 i의 배수에 대하여
				while(mul<1000001) {arr[mul] = false; mul += i;} //소수가 아님을 표시(false)
			}
		}
		
		//정답 출력
		StringBuilder sb = new StringBuilder();
		for(int i=start; i<=end; i++) {
			if(arr[i]) sb.append(i + System.lineSeparator());
		}
		
		System.out.print(sb);
		
		sc.close();
	}

}