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

에라토스테네스의 체 : 소수를 구하는 방법 중 하나

원리

1) 2부터 소수를 구하고자 하는 범위 내의 모든 수를 나열함

2) 2부터 자신을 제외한 2의 모든 배수를 제거함

3) 그 다음으로 남아있는 3을 제외한 3의 모든 배수를 제거함

4) 위의 과정을 반복하여 배수들을 제거함으로써 범위 내에는 소수들만 남게 됨

 

//동적할당 이용

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
int num;
printf(" > 양수 입력 : ");
scanf("%d", &num);

int* pn = (int*)malloc(sizeof(int) * (num - 1));  배열은 2부터 시작하므로 배열 크기 = (num - 2) + 1 = num - 1
if (pn == NULL)
{
printf("#저장공간이 부족합니다...\n");
exit(1);
}

int i, j;

for (i = 0; i < num - 2; i++) 1) 2부터 소수를 구하고자 하는 범위 내의 모든 수를 나열함
{
pn[i] = i + 2;
}



for(i = 0; i < num - 2; i++)   i를 제외한 i의 배수를 제거
{
if (pn[i] == 0) continue;  제거된 숫자들은 i에서 배제됨
for (j = i + 1; j < num - 1; j++)
{
if (pn[j] % pn[i] == 0) pn[j] = 0;
}
}

int cnt = 0; 배열을 5개씩 끊어서 나열하기 위해 cnt 인수 등장

for (i = 0; i < (num - 1); i++)
{
if (pn[i] == 0) printf("%5c", 'X');
else printf("%5d", pn[i]);
cnt++;
if (cnt % 5 == 0) printf("\n");
}

free(pn);
return 0;

}