Thread: sieve of Erotosthenes (HELP!!!)

  1. #1
    Registered User
    Join Date
    Oct 2001

    Question 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:

    #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.

    #define START 2
    #define END 10
    #define SIZE 101
    #define TRUE 1
    #define FALSE 0

    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);

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

    #define SIZE 101
    #define TRUE 1
    #define FALSE 0
    #define START 2

    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);

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

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

  2. #2
    Join Date
    Aug 2001
    Groningen (NL)
    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:

    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Prime Sieve Optimization
    By rt454 in forum C++ Programming
    Replies: 9
    Last Post: 05-30-2008, 10:22 PM
  2. Sieve Of Erastothenes?
    By Neo1 in forum C++ Programming
    Replies: 2
    Last Post: 06-05-2007, 03:09 AM
  3. Primes with Sieve of Eratosthenes.
    By opciok95 in forum C Programming
    Replies: 20
    Last Post: 11-15-2005, 11:03 AM
  4. help about sieve algorithm
    By Antigloss in forum C++ Programming
    Replies: 5
    Last Post: 07-15-2005, 01:58 PM
Website Security Test