Sieve Of Erastothenes?

This is a discussion on Sieve Of Erastothenes? within the C++ Programming forums, part of the General Programming Boards category; Im trying to determine prime numbers with this program, but the output i get is plain wrong. Code: #include <iostream> ...

  1. #1
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964

    Sieve Of Erastothenes?

    Im trying to determine prime numbers with this program, but the output i get is plain wrong.

    Code:
    #include <iostream>
    
    bool checkprime(int n, int f);
    
    int main()
    {
        bool numbers[122];
        int i = 2, j = 2;
        
        for(i = 2; i <= 120; i++)
        {
               numbers[i] = false;                                             //Initiate the Bool array//
        }
        
        for(i = 2; i <= 120; i++)
        {
              for(j = 2; j <= 120; j++)
              {
                      if(!numbers[i])
                      {
                                     if(checkprime(i, j))
                                     {
                                                      numbers[i] = true;
                                                      break;
                                     }
                      }
              }
        }
    
        for(i = 2; i <= 120; i++)
        {
               std::cout << i << " : " << numbers[i] << std::endl;             //Print the Bool Array//
        }
    
        std::cin.get();
    }
    
    bool checkprime(int n, int f)                                              //Function for checking primality//
    {
         if (n % f)
         {
               return(false);
         }
         else
         {
             return(true);
         }
    }
    What am i doing wrong here?

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Because of the way your for loops are set up, eventually, for every i, j will equal i, and calling checkprime(i, i) returns true. This is why you get lots of 1s. But I'm not familiar enough with the algorithm to explain how to fix this issue.

    [edit] Hmm, it looks like you need to eliminate multiples. http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html

    It seems like if you change the second for loop to
    Code:
    for(j = 2; j < i; j++)
    you get the opposite output from what you are expecting -- 7 is 0 but 8 is 1, etc. (Unless maybe that was what you were expecting). This is empirically determined, however, and might be wrong. It makes sense, though, because it avoids the case I mentioned in the first part of this post. [/edit]

    [edit=2] Yes, my fix works. It was just a small flaw in your logic. When you're checking for prime numbers, you want to check the numbers 2 <= x < N, not 2 <= x < infinity. Firstly, because x=N will always be true, as I've already identified, and secondly, because x>N will always be false. Or irrelevant anyway. [/edit]
    Last edited by dwks; 06-05-2007 at 01:34 AM.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Thanks alot Dwks, it's working now, but as you said it's not the output i expected, i'll try and fix that myself though

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, 09:22 PM
  2. Primes with Sieve of Eratosthenes.
    By opciok95 in forum C Programming
    Replies: 20
    Last Post: 11-15-2005, 10:03 AM
  3. help about sieve algorithm
    By Antigloss in forum C++ Programming
    Replies: 5
    Last Post: 07-15-2005, 12:58 PM
  4. sieve of Erotosthenes (HELP!!!)
    By JFK in forum C Programming
    Replies: 1
    Last Post: 02-19-2002, 11:53 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21