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

Posted at 2015.02.13 13:27 | Posted in C



facebook에 글올리기



[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는 소수)


 Colored By Color Scripter

#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으로 초기화를 시킨다.


이웃추가
facebook에 글올리기

Name __

Password __

Link (Your Website)

Comment

SECRET | 비밀글로 남기기