Anyone want to look over my 'extreme newbie' code to calculate prime numbers?

**Dweia** · 11-03-2005

Originally Posted by CrazyNorman

I found a much faster way of doing this a while back.
Create an array of bools, with "upper_limit" elements, with each one equal to 1.
Then, for each number from 2 to upper_limit, if it is equal to 1, go up by it, setting each value above it, which is a multiple of it equal to 1.

*snip*

Basically, you cross out all the multiples of two. Then all the multiples of three. Then, because four has already been crossed out, you don't cross out its multiples (as they would have already been crossed out by two). Just continue this. Thus, multiples of multiples are not tested.

Its reasonably fast, as it takes it 0.05 seconds to find all primes below 100,000 on my machine.

Its possible to optimize my code further using pointer tricks, but I'll keep it simple for you.

Also, if you do not include the printing of the results to std::cout within the timing, it is so fast that it takes 0 seconds according to the timer I am using.

That's known as a Seive of Erosthenes, and is probably the fastest method of generating prime numbers.

Also, you do not need to check every number less than number/2, it's less than sqrt(number), because after you check the square root, any other factor above it must have a matching factor below.

e.g. 36.
Instead of testing up to 18, you only need to test up to 6, because although something like 9 is a higher factor, it has to be paired with a lower number, namely 4.

**CrazyNorman** · 11-03-2005

Thank you for pointing that out. I'm surprised I missed that.

**CrazyNorman** · 11-03-2005

Here is an updated version, using the square root. Wow, it only takes 8.59 seconds (as opposed to 14.4 without) to find all primes below 100,000,000. Thanks for the help.

Code:

#include <iostream>
#include <time.h>
#include <stdio.h>
const unsigned int max = 100000000;

int
main (int argc, char *argv[])
{
  float t, c;
  bool *prime = new bool[max];
  for (unsigned int ctest = 0; ctest < max; ctest++)
    {
      prime[ctest] = 1;
    }
  c = clock ();
  for (unsigned int ctest = 2; ctest < sqrt(max); ctest++)
    {
      if (prime[ctest] == 1)
        {
          for (int citer = ctest * 2; citer < max; citer += ctest)
            {
              prime[citer] = 0;
            }
        }
    }
  int pnum = 0;
  for (unsigned int ctest = 0; ctest < max; ctest++)
    {
      if (prime[ctest] == 1)
        {
          pnum++;
        }
    }
  t = clock () - c;
  t = t / (float) CLOCKS_PER_SEC;
  std::cout << "It took " << t << "seconds" << std::endl;
  std::cout << "There are: " << pnum << " primes below " << max << std::endl;
}

**iclestu** · 11-04-2005

Also, you do not need to check every number less than number/2, it's less than sqrt(number), because after you check the square root, any other factor above it must have a matching factor below.

I might be a newbie and the "Seive of Erosthenes" is definately a new one on me, but I really should have thought of the above! Im annoyed at myself.

Must have been too long since i've been in a maths class.

Thank you to all of you who have given me direction and pointed out the error of my ways

Thread: Anyone want to look over my 'extreme newbie' code to calculate prime numbers?

Thread Tools

Search Thread

Display

Similar Threads

Prime numbers

Prime Numbers

Homework help

Prime Numbers