에라토스테네스의 체

에라토스테네스의 체

• 에라토스텐네스의 체는 소수를 구하는 알고리즘이며, 코딩테스트에서 유용하게 사용된다.

방법

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 2는 소수이므로 오른쪽에 2를 쓰고, 남아있는 수 가운데 2의 배수를 모두 지운다.(빨간색)
3. 3은 소수이므로 오른쪽에 3을 쓰고, 남아있는 수 가운데 3의 배수를 모두 지운다.(초록색)
4. 5은 소수이므로 오른쪽에 5을 쓰고, 남아있는 수 가운데 5의 배수를 모두 지운다.(파란색)
5. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

에라토스테네스의 체.java

package $00_팁;

public class $01_에라토스테네스의_체_소수구하기 {

	public static final int max = 10000;
	
	public static void main(String[] args) {
		
		long start = System.currentTimeMillis();

		boolean[] prime = new boolean[max + 1];
		prime[0] = true;
		prime[1] = true;
		
		for(int i = 2 ; i * i <= max ; i++) {
			if(!prime[i]) {
				for(int j = i * i ; j <= max ; j += i) {
					prime[j] = true;
				}
			}
		}
		
		for(int i = 0 ; i <= max ; i++) {
			if(!prime[i]) {
				System.out.println(i);	// 소수인 수 출력
			}
		}
		
		long end = System.currentTimeMillis();
		System.out.println("수행시간: " + (end - start) + " ms");
        // 10,000 기준 13ms
	}
}