# Prime Number finding Algorithm.How can we make things go faster?

1. Aug 6, 2004

### ExecNight

I am trying to find the best algorithm that will find the prime numbers just for fun..

I am not a programmer so lets talk here in english please..

For example ;

- For the algorithm to run faster it must not calculate even numbers.

a = 1
a = a + 2
the number that will be searched should increase like that..

- The number must first be divided by five..If the result is an integer the program should ignore the rest of the calculations..and return to a = a + 2
so that it can try a new number..

Any more ideas that can speed things up?

2. Aug 6, 2004

3. Aug 6, 2004

### robert Ihnot

After we get past 2, and 3 every prime is of the form $$6x\pm1$$. That eliminates 2/3 of the integers.

Last edited: Aug 6, 2004
4. Aug 6, 2004

### ExecNight

Nice one Muzza very interesting..Though i wonder how is that going to help us when our program reaches a few million digit numbers..

By the way the highest prime number known was something like 6,340,200+ digits if it has not change yet..

Last edited by a moderator: Aug 6, 2004
5. Aug 6, 2004

### Nexus[Free-DC]

That zillion-digit prime is one of a specific type of prime, called a Mersenne prime. Mersenne numbers are of the form 2^k-1 where p is itself some other prime number, and it's easier to verify the primeness of a Mersenne number than it is be to check other numbers of similar magnitude. Mersenne primes are interesting because every one gives you a new perfect number.

That's just an aside though, in case you're interested.

In general, finding prime numbers is very tricky. The Sieve of Eratosthenes requires you to list all the numbers and keep track of the ones you've crossed out, which requires a huge amount of memory. For example, to find all the primes less than one million, you would need to store a million numbers in memory, which turns out to be about 1 meg.

Alternatively, you could try looking at each number in turn, checking to see if it is prime and if it is, storing it to a list. This saves hard disk space but takes a long time because, in general, it is not so easy to determine the primeness of a given number. As Robert Ihnot pointed out, you can skip two out of every three numbers, but that only really helps keep the time down up to a certain point (there's really no difference in waiting around for 3000 years as opposed to 1000).

Some of the more sophisticated algorithms combine both approaches. Say you're trying to determine whether the number x is prime. The algorithm keeps a list of, say, the first 10,000 primes and checks whether x is divisible by any of them. Most values of x will be found to be composite at this point. If not, then the algorithm tries other methods to find factors of x if there are any. These other methods can range from simple-but-slow techniques like checking everything up to sqrt(x), to really sophisticated things that I don't understand.

6. Aug 6, 2004

### robert Ihnot

What to a computer is a large prime today?

There is an article on Public Key Encription:

which discusses a modulus N and key, K, both of which are public. Messages of the form A are raised to the form A^K Mod N and then transmitted. However to read the message you need to know D, such that (A^K)^D==A Mod N. This depends upon finding the primes p and q such that pq = N, since AxD==1 Modulo (p-1)(q-1).

Generally these type of articles say you use "large primes," but what does that mean? Well, this article goes on to say: "If we choose p and q to each be 100 digit prime numbers, which can be easily found, then n is a 200 digit number. Although it takes very little time to multiply p and q to get N, it takes on the order of 4 * 10^9 years on the fastest available machines to factor n back into p and q. For this reason alone, our public key code is secure."

While it has been pointed out by Nexus and ExecNight that special forms such Mersenne numbers have been factored for even 6 million + digits, this article suggests that, while some 100 digit primes are easy to find; a 200 digit number is generally beyond the power of modern computers to factor into two 100 digit primes.

Last edited: Aug 6, 2004
7. Aug 7, 2004

### maverick280857

There's two things to this: generation of prime numbers and primality testing. In principle, they're very similar since you choose a number in the integer sequence and check if its a prime or not. This is the algo we were taught in school:

1. Input n
2. For i = 2 to sqrt(n) or (n/2) repeat steps 3 through
3. Does Rem(n%i) equal zero?
Yeah: n ain't a prime you know and so lets forget it (break out of loop)
Nope: goto step 4
4. Next i
5. Stop

Its not something great considering the better approaches that are known. This is a highly mathematical field though and so it is not possible to avoid using mathematics to come up with algorithms which have smaller complexities.

If you're interested you might want to check this out: http://mathworld.wolfram.com/AKSPrimalityTest.html

8. Aug 8, 2004

### devious_

maverick, you should skip numbers that end in 0, 2, 4, 5, 6 and 8 since they can't be prime. And the loop should be up to sqrt(n). That'll speed it up.

9. Aug 8, 2004

### arildno

10. Aug 8, 2004

### Tom McCurdy

11. Aug 8, 2004

### devious_

Well spotted.

12. Aug 8, 2004

### krab

That's fine if you are looking at the numbers, but in programming is no better than looking for remainder upon division by 2. Computers do not work on base 10 anyway.

13. Aug 8, 2004

### JonF

$$f(j) = \cos^2(\pi*\frac{(j-1)! +1}{j})$$

if 1 <= f(j) < 2 then you have a prime

Last edited: Aug 8, 2004
14. Aug 13, 2004

### maverick280857

All suggestions accepted (since they are correct). The code I gave you though was (as I had said earlier) quite primitive and I added the sqrt(N) to minimize the iterations. Unfortunately, we were discouraged from using too complex algorithms to solve primality testing problems (as we were beginning to use C++ and anything that worked fine--or so it seemed :-D--was okay for the instructors). The code I gave you inherits all the mistakes that you folks have mentioned, from the elementary course that we were taught at school.

If you really want code to test for primes, the mathworld site I mentioned earlier is worth a visit. Thats the best (so far) algorithm that has been written to test primes.

Cheer
Vivek

15. Sep 22, 2008

### alphachapmtl

Yes, it changed one month ago!
On August 23rd, a UCLA computer discovered the 45th known Mersenne prime, 2^(243,112,609)-1, a mammoth 12,978,189 digit number! it's amazing!
http://www.mersenne.org/

16. Sep 22, 2008

### chaoseverlasting

How is that possible? If f(j) is basically a function of cos2x, it mus lie between 0 and 1. It cant ever go beyond that, that exceeds the range of cos2x .

17. Sep 22, 2008

### alphachapmtl

It can't exceed 1, but it can reach it.
This formula is a consequence of Wilson's theorem.
See this reference:
http://mathworld.wolfram.com/PrimeFormulas.html

18. Sep 22, 2008

### CRGreathouse

There have been Mersenne primes discovered since ExecNight posted four years ago, yes...

19. Sep 22, 2008

### HallsofIvy

Staff Emeritus
So you mean "if f(j)= 1"? Why not say that?

$1\le cos^2(x)< 2$
if and only if cos2(x)= 1 which means that x is an integer multiple of $\pi$. Saying that if $1\le f(j)< 2$, with
$$f(j) = \cos^2(\pi*\frac{(j-1)! +1}{j})$$
then j is prime, just say that if ((j-1)!+ 1)/j is an integer then j is prime. That is, if (j-1)!+ 1 is a multiple of j, then j is prime. Was that what you meant?

20. Sep 22, 2008

### alphachapmtl

Yes, that's it. That is Wilson's theorem.
Iff is a prime, then (p-1)!+1 is a multiple of p, that is
(p-1)! = -1 mod p (1)
This theorem was proposed by John Wilson and published by Waring (1770), although it was previously known to Leibniz.
It was proved by Lagrange in 1773.
Unlike Fermat's little theorem, Wilson's theorem is both necessary and sufficient for primality.
For a composite number, (n-1)!=0 mod n except when n=4.
http://mathworld.wolfram.com/WilsonsTheorem.html