C 언어 예제, 에라토스테네스의 체를 이용하여 소수 찾기

목표는 이렇게 만드는 것이다.

크기 제한이 있는데 크기가 정해지지 않은 배열을 만드는 법은 아직 모르고.... 배열 개념을 안 쓰고 하자니 도저히 답이 없어서 이렇게 됐다.

참고로 아주 큰 수를 입력하면 결과가 나오는데 까지 시간이 조금 걸린다. CPU 의 성능을 탓하자.

코드는 이렇다.

/* 에라토스테네스의 체 를 이용한 소수 찾기 */

#include <stdio.h>

int seive(int *arr, int *p, int *q);

int main()

{

int i, j, k, l, m;

int a, b, c;

int arr[100000];

int *p, *q;

printf("몇 이하의 소수를 찾기를 원합니까? 단, 100000 이하의 수에 대해서만 적용 가능합니다.\n");

scanf("%d", &a);

q = &a;

for(i=0;i<a;i++)

{

arr[i] = i+1;

}

for(i=0;i<a;i++)

{

p = &i;

seive(arr, p, q);

}

printf("%d 이하의 소수를 출력합니다. \n",a);

for(i=1;i<a;i++)

{

if(arr[i] != 0)

{

printf("%d ", arr[i]);

}

}

return 0;

}

int seive(int *arr, int *p, int *q)

{

int a, b, c;

int i, j, k;

b = *q;

c = *p+2;

for(i=0;i<b;i++)

{

if(arr[i] % c == 0)

{

if(arr[i] != c)

{

arr[i] =0;

}

}

}

return 0;

}

간략히 설명하자면 이렇다. 에라토스테네스의 체에 따라, 무언가의 배수가 되는 수는 0 으로 만들어 버리고 0은 출력 안 하고 나머지를 출력하면 되는 것이다.

/* 에라토스테네스의 체 를 이용한 소수 찾기 */

#include <stdio.h>

int seive(int *arr, int *p, int *q);

int main()

{

int i, j, k, l, m;

int a, b, c;

int arr[100000];

int *p, *q;

printf("몇 이하의 소수를 찾기를 원합니까? 단, 100000 이하의 수에 대해서만 적용 가능합니다.\n");

scanf("%d", &a);

q = &a;

for(i=0;i<a;i++)

{

arr[i] = i+1;

}

배열 첫 순서는 1부터 시작해야 아귀가 맞으니 arr[i] = i+1;

for(i=0;i<a;i++)

{

p = &i;

seive(arr, p, q);

}

printf("%d 이하의 소수를 출력합니다. \n",a);

for(i=1;i<a;i++)

{

if(arr[i] != 0)

{

printf("%d ", arr[i]);

}

}

0 이 아닌 것을 출력하면 된다.

return 0;

}

int seive(int *arr, int *p, int *q)

{

int a, b, c;

int i, j, k;

b = *q;

c = *p+2;

for(i=0;i<b;i++)

{

if(arr[i] % c == 0)

{

if(arr[i] != c)

{

arr[i] =0;

}

}

나머지가 0 인 것을 출력하면 자기 자신으로 나누어떨어지는 것도 없어지니 전부 0 이 된다. 그러니 자기자신으로 나누어떨어지는 경우만 0 이 되는 것에서 제해 준다.

}

return 0;

}