<Algorithm> 5. 에라토스테네스의 체

에라토스테네스의 체

빠르게 주어진  2부터 N 사이의 소수를 찾을 수 있다.

• 2부터 N 모든 수를 늘어놓는다. 

• 2를 제외한 2의 배수를 지운다.

• 3을 제외한 3의 배수를 지운다.

• 4를 제외한 4의 배수를 지운다.( 2의 배수이므로 이미 걸러짐 )

• 5를 제외한 5의 배수를 지운다. 

• (숫자)^2 > N 전까지 반복

• 지워지지 않은 숫자가 소수이다.

    public static void main(String[] args) {
        int array[]=new int[100];
        for(int i=2;i<100;i++){
            array[i]=i;  // 모두 배열에 저장
        }
        
        for(int i=2;i<100;i++){    
           if(i*i>100)break; // i^2>N 면 반복문 종료
           
            if(array[i]==0)
                continue;
            for(int j=i*2;j<100;j+=i){ // 자기를 제외한 자신의 배수 제거
                array[j]=0;
            }
        }
        for(int i=2;i<100;i++){
            if(!(array[i]==0)){ // 출력
                System.out.print(array[i]+"->");
            }    
        }
    }
}