Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Boolean array to identify prime numbers - C++

  1. Feb 28, 2013 #1
    Hey guys, just looking for an explanation for the following algorithm. It is in my textbook, and there isn't really an explanation. I don't really see how the algorithm works, but I will add what I do know, and hopefully one of you can help. Thanks.

    PHP:


    //this initial declarations produces an array with N elements.
    int N = 40;
    bool table[N];
    int count = 0;

    //this while loop assigns every element in the array to true.
    int i = 0;
    while (i < N)
    {
         table[i]=true;
         i=i+1;
    }

    //from here is where I get lost.
    table[0]=false; //assigns false value to the first element in the array.
    i=2; //starts the next loop at 2.
    while (i < N)
    {
         if (table[i]
         {
              cout << i << " is prime." << endl;
              int j = 2*i;

              while (j < N)
              {
                  table[j]=false;
                   j=j+i;
              }
         }
    i=i+1;
    }
     
    Furthermore, I am not entirely sure why count was initialized at the beginning of the algorithm, I never saw it used.
     
  2. jcsd
  3. Feb 28, 2013 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

  4. Feb 28, 2013 #3

    trollcast

    User Avatar
    Gold Member

    Its basically an implementation of the sieve of eratosthenes method to find primes.
    http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

    The boolean array, table, keeps track of a boolean value for every number up to N that tells whether that number is prime or not. The code then starts from the first prime (2) and excludes all multiples of 2 by setting their boolean value to false. Then the next lowest true value is obviously the next prime, then it repeats this for this number and excludes all its multiples in the table. So then it keeps repeating this process until it reaches the end of the array.
     
  5. Feb 28, 2013 #4
    Perfect, thanks!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Boolean array to identify prime numbers - C++
  1. Prime number test (Replies: 4)

Loading...