에라토스테네스의 체

위는 에라토스테네스의 체를 한눈에 보기 쉽게 만들어진 이미지다.

 

에라토스테네스의 체는 원하는 구간에 소수의 수를 구하기위해 만들어진 방법이다.

 

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

- 2~100000

 

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

- 2, 4, 6, 8,.....

 

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

- 3, 6, 9, 12,....

이때 6과 12는 이미 2번에서 지워졌으므로 넘어간다. 즉, 모두지울때 남아있는 수들 중에 지우는 것.

 

이렇게 반복하면 남은수가 소수가 된다.

 

단, 위 이미지는 11*11 로 121 > 120 이므로 11보다 작은수의 배수들만 작업하더라도 다 지워진다.

즉 i*i <= n 일때만 반복문을 돌리면 불필요한 반복없이 결과를 도출 해 낼 수 있다는 것이다.

 

아래는 에라토스테네스의 체 코드 예시이다.

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);
		    //소수는 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());

	}
}

1929번 소수 구하기를 풀면서 알게된 내용