소수를 구하는 알고리즘 - 에라토스테네스의 체

소수를 구하는 알고리즘 - 에라토스테네스의 체

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법

 

알고리즘[편집]

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. (보라색)

 

그림의 경우, 11^2 > 120

이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

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

 

* 소수가 되는 수의 배수를 지우면 남은 건 소수가 된다

* 소수가 무엇인지 찾을 필요 없이 2부터 자기 자신을 제외한 배수가 되는 것을 지우면 된다.

 

코드

package com.java.coding;

public class EratosExam {

	static boolean isPrime[];
    
    public static void main(String[] args) throws Exception{
    	isPrime_func(120); //120 소수 찾기
    }
    public static void isPrime_func(int n){ 
        isPrime = new boolean[n+1]; // N번째의 수 까지 받기위해 N+1까지 동적할당
        
        for(int i = 0; i < isPrime.length; i++){
            isPrime[i] = true; // boolean배열의 default값은 false이므로 true로 바꿔주기
        }
        
        // 0과 1은 소수가 아니니깐 false
        isPrime[0] = isPrime[1] = false; 
        
        // 2부터 n의 제곱근까지의 모든 수를 확인
        // or i*i<=n
        for(int i = 2; i <= Math.sqrt(n); i++){
        	// 해당수가 소수라면, 해당수를 제외한 배수들을 모두 false 처리하기
            if(isPrime[i]){ // 2,3,5,7
            	//그 이하의 수는 모두 검사했으므로 i*i부터 시작
                for(int j = i*i; j<= n; j += i){
                    isPrime[j] = false;
                }
            }
        }
        // 소수 출력
        for(int i=1; i<=n;i++){
        	if(isPrime[i]) System.out.print(i+" ");        
        }
    }     
}

 

참고 

https://velog.io/@thsdnjst/Java-%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