-----------------------------------

wtd

Thu Oct 14, 2004 10:08 pm


[Tutorial] Optimizing an iterative search for primes

-----------------------------------

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:

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.

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:

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

Fri Oct 15, 2004 10:18 am



-----------------------------------

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

Fri Oct 15, 2004 1:49 pm



-----------------------------------


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

Sun Oct 17, 2004 12:39 am



-----------------------------------

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

Sun Oct 17, 2004 12:42 am



-----------------------------------

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

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


-----------------------------------

zylum

Mon Oct 18, 2004 1:09 pm



-----------------------------------

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


boolean isPrime(int n) {
	for (int i = 2; i