에라토스테네스의 체

에라토스테네스의 체

에라토스테네스의 체 알고리즘은 소수를 구할 때 사용할 수 있는 알고리즘 입니다.

알고리즘 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
   
   
2. 2는 소수이므로 자기자신을 제외한 2의 배수를 모두 지웁니다.
   
   
3. 다음 남아있는 수(3)은 소수이므로 자기자신을 제외한 3의 배수를 모두 지웁니다.
   
   
4. 다음 남아있는 수(5)는 소수이므로 자기자신을 제외한 5의 배수를 모두 지웁니다
   
   
5. 위와 같은 작업을 10까지 반복했을 때 지워지지않고 남아있는 모든수가 소수입니다.

그렇다면 왜 10까지만 반복하는 걸까 ?  

1. 2를 가지고 위의 작업을 수행하면 2*2, 2*3, 2*4, 2*5... 2*50까지 지워집니다.
2. 다음으로 3을 가지고 작업한다고 했을 때 3*2, 3*3, 3*4, 3*5 .. 3*33까지 지워집니다.
3. 다음으로 5로 수행했을 때 5*2, 5*3, 5*4, 5*5, 5*6... 5*20까지 지워집니다.

3의 배수를 지운다고 했을 때 3*2는 이미 2의 배수이기 때문에 지워지고

5의 배수를 지운다고 했을 때 5*2, 5*3, 5*4는 이미 2 또는 3의 배수여서 지워졌기 때문에 비교의 의미가 없습니다.

즉 11로 위의 작업을 수행한다고 가정한다면 11*10 이하의 자연수에서 소수가 아닌 수들은 이미 다 지워졌기 떄문에 위의 작업은 10까지만 수행하는 것입니다.

구현하기

package BackJoon.수학;
 
import java.util.Scanner;
 
/**
 * 에라토스테네스의 체
 * @author troh
 */
public class Main{
    public static void main(String[] args) {
        boolean[] check = new boolean[101];
        
        // 소수의 배수를 모두 체크
        for(int i=2; i<=10; i++) {
            if(!check[i]) {
                for(int j=i+i; j<101; j=j+i) {
                    check[j] = true;
                }
            }
        }
        
        // 소수출력
        for(int i=1; i<=100; i++) {
            if(i == 1) continue;
            
            if(!check[i]) {
                System.out.println(i);
            }
        }
    }
}