에라토스테네스의 체란?

소수를 판별하는 알고리즘이다.

대량의 숫자들에서 소수를 빠르고 정확하게 구하는 알고리즘이다.

에라토스테네스의 체 원리

주어진 숫자만큼의 배열을 생성한 후 소수가 아닌 자리의 값을 변경해가는 방법이다.

1. 주어진 숫자와 동일한 크기의 배열을 생성한 후 초기화한다.
2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.
   • 이 때 자기 자신은 지우지 않고, 이미 지워진 수는 건너뛴다.
3. 2부터 시작하여 남아있는 수를 모두 출력한다.

2부터 30까지의 수에서 소수만 구해보자.

int size = 31;
boolean[] prime = new boolean[size];  // index가 30까지 존재하도록 선언

// 0, 1은 소수가 아니므로 제외
prime[0] = prime[1] = true;

for(int i = 2; i <= size; i++) {
	// 만약 index가 소수라면 break
	if(prime[i])
		continue;

	// 소수가 아닌 index는 제거
	for (int j = i*2; j <= size; j+=i){
		prime[j] = true;
	}
}

예시를 들어보자.

• i = 2 일 경우

  4 <= j <= 31 (j는 2씩 증가 -> j = 4, 6, 8, 10, … )
  
  4 = 2 + 2
  6 = 2 + 2 + 2
  8 = 2 + 2 + 2 + 2 
    …  
  30 = 2 x 15 (2의 배수)
  
  ⇒ 주어진 범위 내에서 2를 제외한 2의 배수에 for loop을 통해 접근 가능
  

• i = 3 일 경우

  6 <= j <= 31 (j는 3씩 증가 -> j = 6, 9, 12, 15, ... )
  
  6 = 3 + 3
  9 = 3 + 3 + 3
    …  
  
  ⇒ 주어진 범위 내에서 3을 제외한 3의 배수에 for loop을 통해 접근 가능
  

• i = 4 일 경우

  8 <= j <= 31 (j는 4씩 증가 -> j = 8, 12, 16)
  
  ⇒ i부터 소수가 아니므로 실행할 이유가 없다.
  ⇒ 2의 배수와 동일하므로 이미 제거되어서 실행할 이유가 없다.
  

⇒ 주어진 범위 내에서 i를 제외한 i의 배수에 for loop을 통해 접근 가능(단 i는 소수)