에라토스테네스의 체

* 에라토스테네스의 체

고대 그리스의 수학자인 에라토스테네스가 발견한 소수(1과 자기자신으로만 나누어지는 수)를 찾는 방법이다. 

내용은 다음과 같다. 

- 알고리즘 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 

2. 2는 소수이므로 오른쪽에 2를 쓴다. 

3. 자기 자신을 제외한 2의 배수를 모두 지운다. 

4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. 

5. 자기 자신을 제외한 3의 배수를 모두 지운다. 

6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. 

7. 자기 자신을 제외한 5의 배수를 모두 지운다. 

8. 위 과정을 계속 반복하면 원하는 구간의 모든 소수가 남는다. 

 

이 때, 100까지의 소수를 구할 때 어디까지 위의 방법을 반복해야 할까? 예를 들어서 17의 배수인 34, 51 등을 지우거나 지워야하는지 확인할 필요가 있을까? 정답은 구하는 수의 제곱근까지만 반복하면 된다. 예를 들자면 100을 구할 때는 10까지만 반복하면 된다. 

 

* 코드

- JAVA

public class Eratos {
	public static void main(String[] args) {
		// ArrayList로 구현
		ArrayList<Boolean> primeList;

		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();

		// n <= 1 일 때 종료
		if(n <= 1) return;

		// n+1만큼 할당
		primeList = new ArrayList<Boolean>(n+1);
		// 0번째와 1번째를 소수 아님으로 처리
		primeList.add(false);
		primeList.add(false);
		// 2~ n 까지 소수로 설정
		for(int i=2; i<=n; i++ )
			primeList.add(i, true);

		// 2 부터  ~ i*i <= n
		// 각각의 배수들을 지워간다.
		for(int i=2; (i*i)<=n; i++){
			if(primeList.get(i)){
				for(int j = i*i; j<=n; j+=i) primeList.set(j, false);
				//i*i 미만은 이미 처리되었으므로 j의 시작값은 i*i로 최적화할 수 있다.
			}
		}
		StringBuffer sb = new StringBuffer();
		sb.append("{");
		for(int i=0; i<=n; i++){
			if(primeList.get(i) == true){
				sb.append(i);
				sb.append(",");
			}
		}
		sb.setCharAt(sb.length()-1, '}');

		System.out.println(sb.toString());

	}
}