### Thread: Program and algorithm to find large digit prime numbers?

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2010
Posts
11
Rep Power
0

#### Program and algorithm to find large digit prime numbers?

How do i write a program to find a large prime number. suppose user wants to find a prime number with 40 digits or even more.
2. The problem here is not the prime number itself, but representing the 40 digit number.
3. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2009
Posts
194
Rep Power
74
Reflect first on what a prime number is, and it's possible range.

1) A prime number can never be even, after the prime number 2. So that cuts your checking in half.

2) A number being checked, only needs to be checked up to (and including), the square root of said number. No higher.

3) Only prime numbers need to be used in checking if another number is prime.

Say I want to check the number 11. Only the number 3 has to be checked, since it is the only (odd) prime number, less than the square root of 11.

As each new prime number is found, you save it in a big array, for fast reference.

Now that's cutting down the workload, a bunch - and much more so, when you get into the higher numbers, where the prime numbers are far more spread out.

A smarter program like this, will typically be hundreds of times faster, than a dumb program, just going to 1 billion.

For working with bigger numbers, use a big number library, like GNU'S big number library. Also, check Wikipedia, etc., for more algorithm tips.

Edit: I found these links for a much faster algorithm:

The fastest method to check for primality discovered so far is the AKS algorithm. Please see the paper "PRIMES in P" at http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf
for the algorithm with its proof and

http://islab.oregonstate.edu/koc/ece575/04Project2/Halim-Chanleudfa/Report.pdf for an implementation of the same in C.

Some introductory notes for this work may be found at http://mathworld.wolfram.com/news/2002-08-07/primetest/

I did a search on Google, looking for an old program of mine - I didn't find it, but there are millions of programs out there for this. None of them in the three pages I checked, were as fast as the algorithm discussed above, except the AKS one. AKS is seriously fast, but a bit above my mathematical "pay scale". ;) ;)
Last edited by Adak; December 6th, 2010 at 03:31 AM.