This is a little something I’ve been working on for an experiment.
It’s a pretty basic prime number generator. At the moment, it’s using what I call, an “exponential” search function which I thought of. It’s probably been thought of by someone else, but I’m calling it my own for the time being.
In my first attempt, generating all prime numbers between 1 and 100000 takes 272 seconds… I didn’t think this was out of the ordinary until a friend told me they did the same in 2.7 seconds!!! Not fair. After going over and over my code, it’s now down to about 0.9 seconds (yay, PHP is faster than Scala!). Turns out, my stupidity was to blame, as I had for some idiotic reason, created my PRIMES array as a global variable. Simply removing the global call, dropped the time from 272 seconds to 0.9… Win.
In the crux of it, the key part of my “algorithm” is this one:
while ($i < sizeof($PRIMES) && $PRIMES[$i]
Outputting the value of $i after the while loop, I was able to show how many iterations are used for each number we are checking. It is important to note, that whilst I am looking for all primes between x and y, we are incrementing the number to check by 2 – not 1. Except for 2, every prime number is an odd number!! This means, the total number of values being checked is very close to y/2.
For x=1 and y=100000, outputting $i and calculating the average value of $i returns 13. The maximum number of iterations is 65. This is due to the while condition I crafted for this. Instead of checking every possible combination between 1 and $CURRENT (the number we are checking), we only need to check every possible number up to a certain value. That is, when the current number, divided by the prime we are dividing by, is greater than that prime (i.e. $PRIME > $CURRENT/$PRIME), than it is certain that the current number is not divisable by any more larger numbers. For example, testing 100 to see if it is a prime, the loop would stop when the prime number being checked is 11, as 100/11 returns a value less than 11 – remember we don’t test 10, because 10 is not a prime.
Pretty graph showing a scatter plot – x axis is the current number, y is the number of iterations. A logarithmic trend line is also shown (although not very visible).
EDIT:
Found 5761455 prime numbers between 1 and 100000000
Took 2384.6677 seconds.
http://en.wikibooks.org/wiki/Efficient_Prime_Number_Generating_Algorithms – pg7.8 algorithm takes 2752 seconds, and is written in Python. My algorithm is written in PHP – admittedly a bad decision, but still faster.
To do:
- Cache generated primes for next runtime
- Improve the search algorithm
Assumptions/constants:
- A prime number is only divisible by 1 and itself (constant)
- A prime number will never end in 0, 2, 5, and the sum of all digits in the number must not be divisible by 3 (constant)
- Except for 1, a prime number can never be a square, or have a square root equal to a whole number (constant)
- When dividing a candidate to test if it is a prime, the only numbers worth testing are prime numbers themselves (constant)
- My code is correct (assumption)