[Java] 백준 1929번 : 소수 구하기

1. 문제

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

1929번: 소수 구하기

 

 

 

2. 풀이 과정

*Key : 에라토스테네스의 체 (소수인 수만 남기기)

 

1) 두 수의 차이 크기인 배열을 생성한다. 5, 10는 배열에서 각각 -5를 해서 0, 5 인덱스를 사용한다.

2) 소수를 구하는 방법은 에라토스테네스의 체를 이용한다.

 

 

*에라토스테네스의 체란?

n의 제곱수 이하인 수중에서 소수를 찾아서 그 소수의 배수를 제거하면 n 이하에 있는 소수를 구할 수 있다.

자세한 설명은 아래의 사이트를 이용하였다.

제곱수 이하인 수만 고려하는 이유는 그 이상의 소수의 배수는 이미 제거되었기 때문이다.

 

n의 제곱수가 기준이므로 이를 소수 k라고 하면 ,소수 k의 배수 = (어떤 수)*(소수 k)이다. 여기서 (어떤 수) < (소수 k) 인 경우는 위에서 말했 듯 우리가 제거해주었다.(어떤 수)=(소수 k)인 경우가 제곱을 의미한다. 따라서 이는 n = (소수 k)*(소수k)와 같은 의미이다.(어떤 수)>(소수 k)인 경우의 수들은 n보다 크기 때문에 고려할 필요가 없는 것이다.

 

namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

에라토스테네스의 체 - 나무위키

 

 

[전체 코드]

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int M = sc.nextInt(), N = sc.nextInt();
		int j, arr[]=new int[N-M+1];
		
		if(M==1)
			arr[0]=-1;
		
		for(int i=2;i<=(int)Math.sqrt(N);i++) {
			for(j=2;j<i;j++) {
				if(i%j==0)
					break;
			}
			
			if(j==i) {//소수인 경우
				for(int k=M/j;k<=N/j+1;k++) {
					if(k<=1)
						continue;
					if(M<=k*j&&k*j<=N) {
						arr[k*j-M]=-1;
					}
				}
				
			}
		}
		
		//소수인 수(배열 값이 0인 수) 출력
		for(int i=M;i<=N;i++) {
			if(arr[i-M]==0)
				System.out.println(i);
		}
	}

}