[Tutorial] Optimizing an iterative search for primes

[wtd]

A prime number is a number where the only factors are that number, and one.

The obvious way to determine if a number N is prime is to count from 2 to N-1, and each time check to see if N can be evenly divided by that number.

The first optimization

First, we need not check all of the numbers. As soon as we've discovered that the number can be evenly divided by another number, we know it's not prime, and our search can stop.

So our code looks something like:

code:

function isPrime(n : int) : boolean    for i : 2 .. n - 1      if n mod i = 0 then          result false       end if    end for    result true end isPrime

The second optimization

If 2 is a factor of N, then the other factor would be N/2. This is the highest factor possible. Anything higher cannot be a factor. So immediately we can make our loop shorter.

code:

function isPrime(n : int) : boolean    for i : 2 .. n div 2      if n mod i = 0 then          result false       end if    end for    result true end isPrime

Third times's a charm

Now, let's say we rule out everything above N/2 when the lowest possible factor is 2. Well, if 2 isn't a factor of N, we move onto 3. Now, there can't be anything above N/3. Similarly, if we move onto 4, then N/4 is the highest possible factor.

So we can optimize this down to:

code:

function isPrime(n : int) : boolean    factor : int := 2    loop       exit when factor >= n div factor       if n mod factor = 0 then          return false       end if       factor += 1    end loop    result true end isPrime

The end result

The loop to test whether there are any factors of N is made as short as possible, and as many numbers as possible are eliminated from the check without overly complicating the code.

[Martin]

A prime number is a number where the only positive factors are that number, and one.

I know, I'm a jerk. Nice tutorial. If anyone is interested helping in a search for the 42nd mersenne prime (primes in the form 2^n - 1), check this out. http://www.mersenne.org/prime.htm

Also, if interested, here is Euclid's proof that there are infinitely many primes:

We know that the list of primes is not empty, as 2, 3, 5, 7, 11 etc. are all prime.
Suppose that the list is finite, that is all of the primes are p1, p2, p3, ..., pk, where pk is the largest prime.

Let n = (p1)(p2)...(pk) - 1

No pi (that's p subscript i, not 3.14159....) can divide n. This is because they can all divide n + 1, and if a prime could divide n+1 and n, then it must divide their difference, which is 1. Clearly, this is not possible (and this is also why 1 is not prime). However, there must be some prime that divides n, even if n is that prime. This prime is not in our list, so a contradiction occurs, and hence, there are infinite primes.

And Dan, please look into getting latex support for our board, this stuff is way too confusing without it.

[Dan]

Martin wrote:

And Dan, please look into getting latex support for our board, this stuff is way too confusing without it.

Do you have a link?

[Hikaru79]

I sure do LaTeX would be a huge help considering how much math-related talk goes on here

http://www.artofproblemsolving.com/LaTeX/AoPS_L_About.php

I hope that link has info about implementing it server-side as well...

[wtd]

http://phpbb.com/phpBB/viewtopic.php?t=167481&highlight=latex

http://phpbb.com/phpBB/viewtopic.php?t=74918&highlight=latex

[zylum]

wouldn't it be much simpler to loop to root n? it's basically the same idea as you presented but simpler to implement.

code:

boolean isPrime(int n) {         for (int i = 2; i <= Math.floor(Math.sqrt(n)); i++)                 if (n % i == 0) return false;         return true; }

[Dan]

wtd wrote:

http://phpbb.com/phpBB/viewtopic.php?t=167481&highlight=latex

http://phpbb.com/phpBB/viewtopic.php?t=74918&highlight=latex

Unfotrly compsci.ca is hosted by a shard hosting comapny. This means i can not iinstall apications on to the server. All of the latex mods for phpbb that i have seen seem to need you to install some progames that i whould not be able to. I will keep looking in to it but i am not shure how i could do it unless the host aggerges to install it for us.

Edit: also it looks like this mod and progame bring up new secuity holes in both the fourm and the server they are instaled on so i am beting the host whould not like that

[Hikaru79]

Wouldn't it be possible (albeit very slow) for the latex tags to send a signal to some volunteer's computer where the text would be parsed, the image would be created and uploaded automatically back to the host and then linked? I know this sort of thing is done for some FTP stat programs, etc.

Or is this just wey to slow to be practical?

[Dan]

It whould be slow, unribleable, unscure and whould eat up bandwith for every one

Also i whould take some considerable moding i think...

[bugzpodder]

zylum wrote:

wouldn't it be much simpler to loop to root n? it's basically the same idea as you presented but simpler to implement.

code:

boolean isPrime(int n) {         for (int i = 2; i <= Math.floor(Math.sqrt(n)); i++)                 if (n % i == 0) return false;         return true; }

a lot more optimizations can be done
first of all, integer multiplication is MUCH MUCH faster than Math.floor(Math.sqrt(n))

something like i*i<=n would do. if you are really worried about overflows, use n/i>=i, still faster than sqrt

and the next thing is, if 2 doesnt divde n, then 4,6,8,... wont divide as well. a simple i+=2 would do the trick.

another less intuitive optimization is, with the exception of 2 and 3, all primes are in the form of 6n+/-1. its obvious that 6n+2, 6n+4 is divisible by 2 and 6n+3 is divisible by 3. with a couple of lines of code you get a faster algorithms.

btw this is only good if you are trying to test if a reasonably small N is prime or not (N<=2^31-1). when N gets bigger more advanced methods should be used. also if you want to find primes in an interval, sieve of Eratosthenes should be used.

another method is store some huge number M which is the product of the first say 1000 primes, and everytime you want to check if N is prime (for a reasonably small N) you use the Euclid Algorithm to compute gcd(N,M)
combined with Fermat's little thoerem for randomly chosen integers this gives industrial grade primality testing (Carmichael numbers c satisfies a^(c-1)=1 (mod c) for gcd(a,c)=1, and c is not prime)

[wtd]

This article is a wonderful addition to this thread.

[bugzpodder]

bitvector/bitarray in STL works nicely if you just want to save space.

also look here: http://home.earthlink.net/~ewill3/math/primecounters/