View Full Version : Urgent: Prime Number Algorithm [C++/pseudocode]

niv

February 14th, 2002, 18:43

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.

niv

February 14th, 2002, 19:24

I do have an algorithm, but take a look at these results:

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: 1.26645e+07

Total resizes: 8

C:\Dev-C++\SRC>

f1done

February 15th, 2002, 02:23

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!

Powered by vBulletin® Version 4.2.2 Copyright © 2014 vBulletin Solutions, Inc. All rights reserved.