Thread: sieve of Erotosthenes (HELP!!!)

Help! Got to procude the following code to replicate the sieve of Eratosthenes. Basically the program looks at numbers 0-100 and filters out the prime numbers. The basic algorithm is cross out multiples of 2 - 10 (so for 2, cross out 2,4,6 etc and for 3, cross out 3,6,9).

The psuedo code is:

#include<stdio.h>
#include<conio.h>
#define SIEVE_SIZE 101
#define TRUE 1
#define FALSE 0
#define START_COUNT 2
#define END_COUNT 10

Initialize sieve array to TRUE
FOR start count to end count
Inner count is equal to count + count
While inner count is less that sieve array size
Sieve array at inner count equals FALSE
Add count to inner count
Output heading text to screen
Initialize number of primes count to 0
For count start to sieve size -1
IF sieve array at count is TRUE
Output count to screen
Increment number of primes
Output closing text to screen

So far I can do the individual bits: This bit identifies all the non primes.

#include<stdio.h>
#include<conio.h>
#define START 2
#define END 10
#define SIZE 101
#define TRUE 1
#define FALSE 0

main()
{
int array[SIZE];
int inner_count = 0;
int count;
int counta;

for(count = START; count <= END; count++)
{
inner_count = count + count;
while(inner_count < SIZE -1)
{
inner_count = inner_count + count;
printf("%d ", inner_count);
}
}
getch();
}

This bit changes the array to be TRUE and count the number of primes:

#include<stdio.h>
#include<conio.h>
#define SIZE 101
#define TRUE 1
#define FALSE 0
#define START 2

main()
{
int myarray[SIZE];
int count, counta, prime, inner_count;

for(count = 0; count < SIZE; count++)
{
myarray[count] = TRUE;
inner_count = START + START;
}
prime = 0;
for(counta = 0; counta < SIZE - 1; counta++)
if(myarray[counta] == TRUE)
{
prime ++;
printf("%d ", counta);
}
printf("\n\nNumber of Primes %d", prime);
getch();
}

I can't seem to put it together and make it work!!

I'd really apreciate some help, anyone got any suggestions???

I would suggest you put the existing code away and design an algorithm. Implement this algorithm and test it. Don't try to put code together you don't understand, it will result in a lot of mess and frustration.

Let me give you a little hint. You need to cross out multiples of 2 until 10. Let N be a number within the range 2..10. Let A be a number in the range 0..100. If A is a multiple of N, then

(A % N) == 0

So a possible, not very efficient, algorithm would be:

Code:

for A = 3 to 100
    for N = 2 to 10
        if (A mod N == 0) then 
            cross A

Note that A should start with 3, since else 2 will be crossed out, but 2 is a prime number.