#1
  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. #2
  3. Hats off to Mr. Joseph donahue
    Devshed Novice (500 - 999 posts)

    Join Date
    Aug 2009
    Posts
    752
    Rep Power
    1106
    The problem here is not the prime number itself, but representing the 40 digit number.
    Read about Arbitrary-precision arithmetic
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2009
    Posts
    194
    Rep Power
    71
    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.

IMN logo majestic logo threadwatch logo seochat tools logo