Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
[tutorial] Finding a Prime number
Author Message
Tony

Posted: Fri Feb 14, 2003 3:51 pm   Post subject: [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.

 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

tony.t
Description:
 Tony's Prime Number Finder program - includes file output with a timer.

Download
Filename:  tony.t
Filesize:  516 Bytes
Downloaded:  608 Time(s)

Tony's programming blog. DWITE - a programming contest.
Sponsor
Sponsor

Crono

Posted: Fri May 09, 2003 4:53 pm   Post subject: 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

Posted: Fri May 09, 2003 5:22 pm   Post subject: (No subject)

even better, thx for pointing this out Crono +5Bits
Tony's programming blog. DWITE - a programming contest.
Dan

Posted: Fri May 09, 2003 8:44 pm   Post subject: (No subject)

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
Computer Science Canada Help with programming in C, C++, Java, PHP, Ruby, Turing, VB and more!
Tony

Posted: Fri May 09, 2003 10:16 pm   Post subject: (No subject)

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
Tony's programming blog. DWITE - a programming contest.
Hikaru79

Posted: Wed Apr 27, 2005 5:41 pm   Post subject: (No subject)

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

Posted: Thu Apr 28, 2005 10:01 am   Post subject: (No subject)

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
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 7 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: