에라토스테네스의 체
에라토스테네스의 체 알고리즘은 소수를 구할 때 사용할 수 있는 알고리즘 입니다.
알고리즘
- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
- 2는 소수이므로 자기자신을 제외한 2의 배수를 모두 지웁니다.
- 다음 남아있는 수(3)은 소수이므로 자기자신을 제외한 3의 배수를 모두 지웁니다.
- 다음 남아있는 수(5)는 소수이므로 자기자신을 제외한 5의 배수를 모두 지웁니다
- 위와 같은 작업을 10까지 반복했을 때 지워지지않고 남아있는 모든수가 소수입니다.
그렇다면 왜 10까지만 반복하는 걸까 ?
- 2를 가지고 위의 작업을 수행하면 2*2, 2*3, 2*4, 2*5... 2*50까지 지워집니다.
- 다음으로 3을 가지고 작업한다고 했을 때 3*2, 3*3, 3*4, 3*5 .. 3*33까지 지워집니다.
- 다음으로 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까지만 수행하는 것입니다.
구현하기
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | 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); } } } } | cs |