에라토스테네스의 체

에라토스테네스의 체

소수를 구하는 알고리즘.

📌알고리즘

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 2는 소수이므로 자기 자신을 제외한 2의 배수를 모두 지운다.
3. 남아있는 수 가운데 3은 소수이므로 자신을 제외한 3의 배수를 모두 지운다.
4. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

📌구현

code

int [] prime = new int[N+1];

for(int i = 2; i <= N; i++) {
	if(prime[i]==1) continue;
	for ( int j = i*2; j <=N; j+=i) [
		prime[j]=1;
  }
}