[Algorithm] 에라토스테네스의 체, 소수찾기 feat. Java

소수(Prime Number)

소수란 보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다.

예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 6은 자신보다 작은 두 숫자의 곱(2×3)이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다.

 

에라토스테네스의 체

소수를 빨리 찾을 수 있는 알고리즘이다.

 

과정

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 자기 자신을 제외한 2의 배수를 모두 지운다.
3. 자기 자신을 제외한 3의 배수를 모두 지운다.
4. 자기 자신을 제외한 5의 배수를 모두 지운다.
5. 자기 자신을 제외한 7의 배수를 모두 지운다.
6. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

이미지

코드

public class Main {

	//100000 까지의 소수를 구하기 위해 100001 선언.
	static boolean prime[] = new boolean[100001];
    
    public static void main(String[] args) throws Exception{
		
        // 구하고자 하는 숫자 범위
        int N = 100000;
        
        // 소수는 false
        // 1은 소수가 아니므로 제외
        prime[0] = prime[1] = true;
        
        for(int i=2; i*i<=N; i++){
        	// prime[i]가 소수라면
            if(!prime[i]){
            	// prime[j] 소수가 아닌 표시
            	for(int j=i*i; j<=N; j+=i) prime[j] = true;                
            }        
        }    
        
        // 소수 출력
        for(int i=1; i<=N;i++){
        	if(!prime[i]) System.out.print(i+" ");        
        }
        
    }
}

 

참고

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전