1. Howdy! Welcome to our community of more than 100.000 members devoted to web hosting. This is a great place to get special offers from web hosts and post your own requests or ads. To start posting sign up here. Cheers! /Peo, FreeWebSpace.net

Urgent: Prime Number Algorithm [C++/pseudocode]

Discussion in 'General Discussions' started by niv, Feb 14, 2002.

  1. niv

    niv striking reality NLC

    Messages:
    7,344
    Likes Received:
    2
    Trophy Points:
    0
    Anyone know how to generate all the primes less than n in a relatively quick fashion? If I were to use nested loops, I'll get points taken off for efficiency...I'm looking for a linear algorithm.

    C++ code is welcomed, but pseudocode explanations are as well.
     
  2. niv

    niv striking reality NLC

    Messages:
    7,344
    Likes Received:
    2
    Trophy Points:
    0
    I do have an algorithm, but take a look at these results:

    Code:
    C:\Dev-C++\SRC>16
    Enter the limit for which odd psuedo and regular prime numbers
    less than this number will be found: 30
             1                   3
             2                   5
             3                   7
             4                  11
             5                  13
             6                  17
             7                  19
             8                  23
             9                  29
    Total comparisons: [b]1.26645e+07[/b]
    Total resizes: 8
    
    C:\Dev-C++\SRC>
    
     
  3. f1done

    f1done New Member

    Messages:
    22
    Likes Received:
    0
    Trophy Points:
    0
    Why not nested loops? If they're what I think they are (for x do [for x do ...]), they should run okay. I made one for PHP, which runs upward through the numbers (okay, starting from 4, I cheated with the first two), and then finds the denominator for the modulus by calculating every number less than the square root of the first number- if none of them are 0, then it's prime. It did 1-1000 in about 0.07 seconds (I'm using an old Celeron 400, so on the modern day computers it would probably run faster...). I did leave it to calculate all primes from 1 to one million, but it took something like 11 minutes (wonder what my web host would say if I uploaded that on their server :D LOL). Still, it ran a lot faster than my friend's Javascript version, which took about 15 seconds for 1-1000!
     
    Last edited: Feb 15, 2002

Share This Page