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

  • Thread starter ExecNight
  • Start date
  • Tags
    Prime
In summary, the conversation discusses different approaches for finding prime numbers, including using the Sieve of Eratosthenes and algorithms such as the AKS primality test. The conversation also touches on the difficulty of factoring large numbers into primes and the importance of finding large primes for public key encryption. The participants also mention the use of mathematical knowledge and algorithms to improve the efficiency of finding prime numbers.
  • #1
ExecNight
I am trying to find the best algorithm that will find the prime numbers just for fun..


I am not a programmer so let's 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?
 
Mathematics news on Phys.org
  • #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:
  • #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:
  • #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.
 
  • #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:
  • #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 let's 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
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
devious_ said:
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.
What about 2? :wink:
 
  • #10
there is a book written on all of this you may want to check out... unfortunately i have yet to read it to tell you of the quality, but i attended a lecture while in england and the author was the lecturer

here is the link to amazon
 
  • #11
arildno said:
What about 2? :wink:

Well spotted. :approve:
 
  • #12
devious_ said:
maverick, you should skip numbers that end in 0, 2, 4, 5, 6 and 8
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
[tex] f(j) = \cos^2(\pi*\frac{(j-1)! +1}{j}) [/tex]

if 1 <= f(j) < 2 then you have a prime
 
Last edited:
  • #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.

Cheer
Vivek
 
  • #15
ExecNight said:
By the way the highest prime number known was something like 6,340,200+ digits if it has not change yet..
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
JonF said:
[tex] f(j) = \cos^2(\pi*\frac{(j-1)! +1}{j}) [/tex]

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

How is that possible? If f(j) is basically a function of cos2x, it mus lie between 0 and 1. It can't ever go beyond that, that exceeds the range of cos2x .
 
  • #17
chaoseverlasting said:
How is that possible? If f(j) is basically a function of cos2x, it mus lie between 0 and 1. It can't ever go beyond that, that exceeds the range of cos2x .
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
alphachapmtl said:
ExecNight said:
By the way the highest prime number known was something like 6,340,200+ digits if it has not change yet..
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/

There have been Mersenne primes discovered since ExecNight posted four years ago, yes...
 
  • #19
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?
 
  • #20
HallsofIvy said:
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?
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
 
  • #21
alphachapmtl said:
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

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?
 

1. What is a prime number?

A prime number is a positive integer that is only divisible by 1 and itself. Examples of prime numbers include 2, 3, 5, 7, and 11.

2. How do prime number finding algorithms work?

Prime number finding algorithms use mathematical techniques to efficiently search for and identify prime numbers within a given range. These algorithms typically involve checking if a number is divisible by any smaller numbers, and if not, it is considered a prime number.

3. What is the most commonly used prime number finding algorithm?

The Sieve of Eratosthenes is one of the most commonly used prime number finding algorithms. It involves creating a list of numbers and systematically eliminating all the multiples of each prime number until the list contains only prime numbers.

4. How can we improve the speed of prime number finding algorithms?

One way to improve the speed of prime number finding algorithms is to use more efficient data structures and techniques, such as using sieves or parallel processing. Another approach is to optimize the code and reduce the number of unnecessary calculations.

5. Are there any limitations to prime number finding algorithms?

While prime number finding algorithms have greatly improved over time, there are still limitations in terms of the size of numbers that can be checked for primality. As numbers get larger, the time and resources required to find prime numbers also increase. Additionally, there are some complex numbers for which primality cannot be determined using current algorithms.

Similar threads

  • Programming and Computer Science
Replies
22
Views
633
  • Programming and Computer Science
Replies
14
Views
1K
Replies
3
Views
96
  • Precalculus Mathematics Homework Help
Replies
3
Views
899
  • General Math
Replies
13
Views
1K
  • General Math
Replies
1
Views
1K
Replies
6
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
692
  • Engineering and Comp Sci Homework Help
Replies
1
Views
498
Replies
20
Views
1K
Back
Top