/* The Sieve of Eratosthenes implemented in 'C'
* Robin Broad
* November 2008
* Part of a project to demonstrate an ability to
* implement an algorithm in a range of different
* computing languages and to use a range of
* compilers, including the following:
*
* Java: BlueJ
* C: Miracle C
* C++: Microsoft Visual C++.NET
* C#: Microsoft Visual C#.NET
* Visual Basic: Microsoft Visual Basic.NET
*/
#include <stdio.h>
#include <math.h>
#define RANGE 255 //we are calculating the prime numbers up to this number
main()
{
//variable declarations
int listOfIntegers[RANGE];//This array of integers will hold all the numbers up to the value of RANGE
int root=(int)sqrt((double)RANGE);//needed later on when removing multiples, casting is used since we're
//only interested in integer values
int product=0;//used later when removing multiples
int printCount=0;//used during print formatting of the program output
int n,multiplier=0;//used a loop counter
//initialising the integer array
for(n=1; n<=RANGE; n++)listOfIntegers[n]=n;
//starting from n=2, "remove" multiples of n up the value of RANGE
//repeat for increasing values of n up to the square root of RANGE
for(n=2; n<=root; n++)
{
//delete the multiples of n
for(multiplier=2; multiplier*n<=RANGE; multiplier++)
{
product=n*multiplier;
listOfIntegers[product]=0;
}
}//end of multiple removal
//print out the prime numbers remaining, remembering that 2 is the first prime number
printf("The Sieve of Eratosthenes program\n");
printf("Written in 'C' and compiled in Miracle C\n");
printf("Robin Broad, November 2008.\n");
printf("The prime numbers in the range: 1 to %d are:-\n",RANGE);
for(n=2; n<=RANGE; n++)
{
//print all non-zero elements of the integer array in blocks of 10 numbers at a time
if (listOfIntegers[n]!=0)
{
printf("%6d\t",listOfIntegers[n]);
printCount++;
if(printCount%10==0)printf("\n");//every 10 items produces a new line
}
}
printf("\n\nEnd of Program.\n\n(Note that a limit on the range of this calculation was limited by the ");
printf("shareware compiler which was unable to support an integer array size greater than 255!)");
getchar();
}//end of main
//Robin Broad, November 2008
/*
*This program produced the following output:
The Sieve of Eratosthenes program
Written in 'C' and compiled in Miracle C
Robin Broad, November 2008.
The prime numbers in the range: 1 to 255 are:-
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 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251
End of Program.
(Note that a limit on the range of this calculation was limited by the shareware
compiler which was unable to support an integer array size greater than 255!)
*/