Sieve of Eratosthenes

In mathematics, the sieve of Eratosthenes, one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e. not prime) the multiples of each prime, starting with the multiples of 2.┬áThe multiples of a given prime are generated starting from that prime, as a sequence of numbers with the same difference, equal to that prime, between consecutive numbers. This is the sieve’s key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.┬áThe sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes (below 10 million or so). It is named after Eratosthenes of Cyrene, a Greek mathematician. [Wikipedia]

Sieve_of_Eratosthenes_animation

Here is the C code for the sieve of Eratosthenes algorithm.

/*
 * Sieve of Eratosthenes
 *  soe_algo.c
 */
#include <stdio.h>
#include <stdbool.h>
#include <math.h>

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

	if (argc<2) {
		printf("This program shows prime numbers up to a certain number \n
			Usage: %s <number> \n ", argv[0]);
		return -1;
	}

	int m, k,  upper_bound = atoi(argv[1]);

	int upper_bound_sqrt = (int) sqrt(upper_bound);

	bool is_composite[upper_bound + 1];

	for (m = 2; m <= upper_bound_sqrt; m++) {
		if (!is_composite[m]) {
			printf("%d ", m);
			for (k = m * m; k <= upper_bound; k += m)
				is_composite[k] = true;
		} // if
	}//for

	for (m = upper_bound_sqrt + 1; m <= upper_bound; m++)
		if (!is_composite[m])
			printf("%d ", m);

	printf("\n");

	return 0;
} // end

Compile using gcc and run it.

gcc -o soe_algo.o soe_algo.c -lm
./soe_algo.o 100

Output: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97.