[C] 소수 출력하기 (에라토스테네스의 체)

[C] 소수 출력하기 (에라토스테네스의 체)

'주어진 N보다 작은 소수를 모두 구하여라'

이것은 2부터 주어진 N까지의 숫자를 탐색하면서, 소수가 아닌 숫자와 그 배수들을 지워나가고 최종적으로 남은 숫자만 출력하는 방법이다.

소수가 아닌 숫자들을 체크하여 지워나가기 위하여 배열을 사용한다.

1. 정수 N을 입력받는다 (N까지의 소수를 구한다)

2. 정수 N만큼의 배열 array[N]을 확보한다.

3. array[N]을 초기화시킨다. (모든 요소를 0으로)

4. for(i=2; i<N; i++)

4.1 만약 array[i] != 0 이면 (즉 소수가 아니라서 지워진 수이면) 4로 돌아간다.

4.2 for(j=i+i; j<=N; j+=i)  (j는 i의 배수)

4.3 array[j]에 1을 대입  (소수가 아니라서 지우는 체크)

5. for(i=2; i<=N; i++)

5.1 array[i]==0 인 i를 출력 (i는 소수)

#include <stdio.h> #include <malloc.h> #include <stdlib.h> #define MAX 9999 void main(void){     int* iptr;     int i, j;     iptr = (int*)calloc(MAX, sizeof(int));     if (iptr == NULL){         puts("\n Memory allocation error !");         exit(1);     }     for (i = 2; i < MAX; i++){         if (iptr[i] == 1)             continue;         j = i;         while ((j += i) <= MAX){             iptr[j] = 1;         }             }     for (i = 2; i <= MAX; i++){         if (iptr[i] == 0)             printf("\t%6d", i);     }     return 0; }

* calloc() 함수는 malloc() 함수와는 달리 메모리를 할당한 다음 할당도니 메모리에 대해서 모두 0으로 초기화를 시킨다.

출처: https://hyeonstorage.tistory.com/338?category=622873 [개발이 하고 싶어요]