----------------------------------- Tony Fri Feb 14, 2003 3:51 pm [tutorial] Finding a Prime number ----------------------------------- 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. 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 :wink: 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 :wink:). 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 :wink: ----------------------------------- Crono Fri May 09, 2003 4:53 pm regarding the program ----------------------------------- 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 Fri May 09, 2003 5:22 pm ----------------------------------- even better, thx for pointing this out Crono :) +5Bits ----------------------------------- Dan Fri May 09, 2003 8:44 pm ----------------------------------- even better, thx for pointing this out Crono :) +5Bits if i suck up to tony can i get more bits too? :lol: j/k ----------------------------------- Tony Fri May 09, 2003 10:16 pm ----------------------------------- well your bits do look low... considering the fact that you're an admin and some users have more bits that you... :shock: +500 Bits Ohh :o ----------------------------------- Hikaru79 Wed Apr 27, 2005 5:41 pm ----------------------------------- 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! :lol: ----------------------------------- Tony Thu Apr 28, 2005 10:01 am ----------------------------------- 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 :lol: