에라토스테네스의 체 (소수 구하기)

소수를 구하는 방법중엔 에라토스테네스의 체 방법이 꽤 효과적이다.

어차피 알고리즘 문제에서도 에라토스테네스의 체 를 응용한 문제가 더 많이 나올 테니 이것을 응용하는게 더 좋음.(TC가 많아도 일단 한번 다 저장하면 장땡이기 때문)

#include<stdio.h>

int N;

int arr[10001];

void prime(int num)

{

for (int i = 0; i < num; i++)

{

arr[i] = i;

}

for (int i = 2; i <= num; i++)

{

if (arr[i] == 0) continue; // 이미 체크된 수의 배수는 skip (이거 지우면 엄청 오래걸림)

for (int j = 2; j <= num; j++)

{

if (arr[j] != i && arr[j] % i == 0){

arr[j] = 0;

}

}

}

}

void main()

{

scanf("%d", &N);

prime(N);

}

그! 런! 데!!!이 방법이 더 좋다. 무조건 이 아래방법을 써야한다.!!!

예를 들어 10000까지의 소수를 구하려한다면, 아래 공식으로 써야한다. 100이라고 쓴 거 잘못쓴거 아님!

{ 

for (int i = 2; i < 100; i++)

{

if (prime[i] == 0) {

for (int j = i*i; j < 10000; j++)

{

prime[j] = 1;

}

}

}

}