Eratosthenes’s sieve (C)

An O(nloglogn) algorithm to find prime numbers, designed by ancient Greek Eratosthenes.
More about the algorithm can be found here (that’s the reason you will see no comments on the code).
This was the algorithm that I used to solve two of the problems of Project Euler. Due to this algorithm, I succeeded in achieving much better performance than the other solutions ( question 7: 40ms and question10 : only 50ms (!) ).


#include <stdio.h>
#include <math.h>
#include <stdbool.h>

void fillTrue(bool *array, const int N);
void input(int* N);
void print(bool *candidates, const int N);
void sieveEratosthenes(bool *candidates, const int N);

int main(void)
    int N;
    bool candidates[N];
    fillTrue(candidates, N);
    sieveEratosthenes(candidates, N);
    print(candidates, N);
    return 0;

void sieveEratosthenes(bool *candidates, const int N)
    int i, j, r;
    for(i = 2,  r = sqrt(N) ; i <= r ; i++)
            for(j = i*i ; j <= N ; j += i)
                candidates[j] = false;

void input(int* N)
        printf("Please, input a positive number\n");
        scanf("%d" , N);
    }while(*N < 0);

void fillTrue(bool *array, const int N)
    int i;
    array[0] = array[1] = false;
    for(i = 2 ; i < N ; i++)
        array[i] = true;

void print(bool *candidates, const int N)
    int i;
    for(i = 0 ; i < N ; i++)
        printf("%d is %sprime\n", i, candidates[i] ? "" : "NOT ");

This code was developed by me, G. Samaras.

Have questions about this code? Comments? Did you find a bug? Let me know! 😀
Page created by G. (George) Samaras (DIT)


One thought on “Eratosthenes’s sieve (C)

  1. Pingback: isPrime

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s