에라토스테네스의 체

 

방법은 여러 가지가 있는 것 같은데, 대표적으로는 아래처럼 쓰인다.

 

1)

prime[0] = prime[1] = true;
	for (int i = 2; i <= sqrt(num); i++){
		if (prime[i] == false){
			for (int j = i + i; j <= num; j += i){
				prime[j] = true;
			}
		}
	}

 

2)

prime[0] = prime[1] = true;
for (int i  = 2; i*i <= num; i++) {
	if (prime[i] == false) {
		for (int j  = i  * i; j  <= num; j += i) {
			prime[j] = true;
		}
	}
}