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

This is a discussion on Anyone want to look over my 'extreme newbie' code to calculate prime numbers? within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by CrazyNorman I found a much faster way of doing this a while back. Create an array of ...

  1. #16
    Cat Lover
    Join Date
    May 2005
    Location
    Sydney, Australia
    Posts
    109
    Quote 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.

  2. #17
    Amazingly beautiful user.
    Join Date
    Jul 2005
    Location
    If you knew I'd have to kill you
    Posts
    254
    Thank you for pointing that out. I'm surprised I missed that.
    Programming Your Mom. http://www.dandongs.com/

  3. #18
    Amazingly beautiful user.
    Join Date
    Jul 2005
    Location
    If you knew I'd have to kill you
    Posts
    254
    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;
    }
    Programming Your Mom. http://www.dandongs.com/

  4. #19
    Registered User
    Join Date
    Nov 2005
    Posts
    7
    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

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Prime numbers
    By Lazy Student in forum C Programming
    Replies: 12
    Last Post: 05-14-2002, 05:53 AM
  2. Prime Numbers
    By cmangel518 in forum C++ Programming
    Replies: 13
    Last Post: 04-30-2002, 11:51 PM
  3. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 04:56 PM
  4. Prime Numbers
    By Korn1699 in forum C++ Programming
    Replies: 7
    Last Post: 11-03-2001, 08:52 PM

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