[tutorial] Finding a Prime number

[Tony]

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

[Crono]

wow, ur algorithm is amazin, from 2 to a million in a mere 5 seconds, that's just plain sweet, it sure beats wutever i even had by minutes

but i wuz just wonderin, if it's necessary to go thru wit all the even #'s, since they're never prime anyhow (cept fo 2), i changed it to "for i : 3 .. 1000000 by 2", and the performance betters by about a second from the original on my 1800+ to bout 4.5 seconds

[Tony]

even better, thx for pointing this out Crono +5Bits

[Dan]

tony wrote:

even better, thx for pointing this out Crono +5Bits

if i suck up to tony can i get more bits too?

j/k

[Tony]

well your bits do look low... considering the fact that you're an admin and some users have more bits that you... +500 Bits Ohh

[Hikaru79]

I know this thread is like a million years ago, but I just read it now and I have to ask...

How is this algorithm any different from the sieve of Eratosthenes? As far as I can tell, it's pretty much the exact same thing. Which is OK, the Sieve is a really important fundamental idea which is probably taught and re-invented in every comp sci course accross the country, but my question is... how on earth did you win a competition with this? Isn't this the first idea that everyone would implement? It's about the most common algorithm I can think of...even Holt's Java textbook talks about it!

[Tony]

Hikaru79 wrote:

Isn't this the first idea that everyone would implement?

Not really. Many people have this urge to divide by a large set of redundant numbers