1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Aug 6, 2004 #1
    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. jcsd
  3. Aug 6, 2004 #2
  4. Aug 6, 2004 #3
    After we get past 2, and 3 every prime is of the form [tex]6x\pm1[/tex]. That eliminates 2/3 of the integers.
    Last edited: Aug 6, 2004
  5. Aug 6, 2004 #4
    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
  6. Aug 6, 2004 #5
    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.
  7. Aug 6, 2004 #6
    What to a computer is a large prime today?

    There is an article on Public Key Encription:
    http://www.cs.usask.ca/resources/tutorials/csconcepts/1999_3/lessons/L5/CreatingPublicKey.html [Broken]

    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 by a moderator: May 1, 2017
  8. Aug 7, 2004 #7
    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
  9. Aug 8, 2004 #8
    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.
  10. Aug 8, 2004 #9


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    What about 2? :wink:
  11. Aug 8, 2004 #10
  12. Aug 8, 2004 #11
    Well spotted. :approve:
  13. Aug 8, 2004 #12


    User Avatar
    Science Advisor

    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.
  14. Aug 8, 2004 #13
    [tex] f(j) = \cos^2(\pi*\frac{(j-1)! +1}{j}) [/tex]

    if 1 <= f(j) < 2 then you have a prime
    Last edited: Aug 8, 2004
  15. Aug 13, 2004 #14
    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.

  16. Sep 22, 2008 #15
    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!
  17. Sep 22, 2008 #16
    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 .
  18. Sep 22, 2008 #17
    It can't exceed 1, but it can reach it.
    This formula is a consequence of Wilson's theorem.
    See this reference:
  19. Sep 22, 2008 #18


    User Avatar
    Science Advisor
    Homework Helper

    There have been Mersenne primes discovered since ExecNight posted four years ago, yes...
  20. Sep 22, 2008 #19


    User Avatar
    Science Advisor

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

    [itex]1\le cos^2(x)< 2[/itex]
    if and only if cos2(x)= 1 which means that x is an integer multiple of [itex]\pi[/itex]. Saying that if [itex]1\le f(j)< 2[/itex], with
    [tex] f(j) = \cos^2(\pi*\frac{(j-1)! +1}{j}) [/tex]
    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?
  21. Sep 22, 2008 #20
    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.
  22. Sep 23, 2008 #21
    Maybe I'm just nitpicking, but how can f(j) be greater than 1? The only possible thing that inequality can mean is f(j)=1. Why not just write that instead?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook