Sieve of Eratosthenes

Overview

에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘 내용 정리.

Basic

에라토스테네스의 체: 121보다 작은 숫자들 중에서 소수를 찾는 예제

범위의 숫자들 중에서 소수를 찾는 알고리즘이다.

어떤 숫자가 소수라면, 당연하겠지만, 소수의 배수들은 소수가 아니다. 따라서 배수가 되는 숫자들을 모두 지워나가면, 남게되는 숫자들은 소수라는 뜻이 된다.

Pseudocode

Input: an integer n > 1
 
Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
 
for i = 2, 3, 4, ..., not exceeding √n:
  if A[i] is true:
    for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n :
      A[j] := false
 
Output: all i such that A[i] is true.

Examples

C

<source lang=c>

1. include <stdio.h>
2. include <stdlib.h>
3. include <stdbool.h>

void eratos(int size) {

   bool* numbers;
   int ret;
   int i;
   int j;
   
   // check input parameter.
   if(size < 1) {
       printf("Invalid input.\n");
       return;
   }
   
   numbers = calloc(sizeof(char), size + 1);
   
   // initialize.
   for(i = 0; i < size + 1; i++) {
       numbers[i] = true;
   }

   // The 0 is not prime number.
   // The 1 is prime number.
   printf("Found prime number. number[%d]\n", 1);
   
   for(i = 2; i < size + 1; i++) {
       if(numbers[i] == false) {
           continue;
       }
       
       // set all false of multiply.
       for(j = i + 1; j < size + 1; j++) {
           ret = j % i;
           if(ret == 0) {
               // not prime number.
               numbers[j] = false;
           }
       }
       printf("Found prime number. number[%d]\n", i);
   }
   
   free(numbers);

}

int main(int argc, char** argv) {

   if(argc < 2) {
       printf("Usage: ./main <size of numbers>\n");
       return 0;
   }
   
   eratos(atoi(argv[1]));
   return 0;

} </source>