We had a little competition on who can find prime numbers faster... so I desided it would be a good idea to post a tutorial about my winning code algorythm.
First of all, a prime number is a number that can be divided without a remainder only by 1 and itself.
By running a forloop and dividing it by every number, you can see if you can divide it by anything else or not.
| code: |
var num :int = 9 for i:2..num-1 if num mod i = 0 then put num, "is not prime" exit end if end for |
but this method is very unefficient... sure it might be fine to check one small number... but what if you need to find ALL the prime numbers in a range from 2 to 100,000 ? Then every single if statment counts. Try running an if statment million times... you'd have to wait, wouldn't you?
Brightguy came up with a more efficient solution to the problem by cutting lots of corners... and in programing thats a good thing
| code: |
for n:2..100000 %number to check for prime var a : real := 1 loop a += 1 %number to divide by if a > sqrt (n) then /*if the number reached more then square root of the number we're checking, without exiting the loop, then it must be prime*/ put n, " is prime" exit %go on to next number end if exit when n mod a = 0 /*if number divides without a remainder, then its not prime... exit loop and go to next number*/ end loop end for |
This code is more efficient because it doesn't do the unnesesary calculations we had in first version. It checks only up to square root of the number since you know square root of the number is the max you can possibly divide by... If we're finding out if 1,000,000 is a prime or not, that will save us 999,000 operations since we need to check only up to 1,000. Thats 1000times more efficient (fast). It will also exit the loop as soon as it finds out the number is not prime... so for 1,000,000 it will exit after a single if statment because it divides by 2.
The problem is that to confirm that 99991 is prime (and it is) you still have to go through almost 1,000 if statments. That will cost you your valuable time.
Thats where Tony's algorythm comes in... this works in a totaly different way.
Instead of confirming that each number is indeed prime or not, we set up an array and systematicly (or something like that) take out blocks of numbers that are NOT prime.
What I mean is lets say we take a first number... its 2 (all prime algorythms start with 2... because we know that 1 is not it
). Now the number itself is prime, but all of its multiples are NOT. If a number has multiples, then you can divide that multiple by original number without a remainder so its NOT prime.
this step will kick out 4,6,8,10,12,14,16,18,20,22,24 (we're doing an example of up to 25)
move on to next number... 3... it was not marked as not prime yet, so its prime... but all of its multiples are not.
6,9,12,15,18,21,24 are NOT prime.
move on to 4. Its marked as NOT prime... so since all the multiples of 4 are also multiples of 2 we don't need to run the loop since they are all marked out already.
but 5 is not. 5 stays prime but 10,15,20,25 are not.
and we stop on 5 since its a square root of 25 (or final number)... no further number can possibly divide by anything larger then 5 and was not marked NOT prime yet.
After we just see what numbers are not yet marked NOT prime yet... those are PRIME and the list from 2 to 25 are:
2,3,5,7,11,13,17,19,23.
You can download the program from the file attached. It will list all of prime numbers from 2 to 100,000 in 2 seconds (on Celeron 550).
Largest prime is 99,991 ... You can check that using first program and time how long it takes just to confirm that its in fact prime... And now compare to my program telling you ALL of the prime numbers in that range
