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

[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?

 

[Muzza]

Check out the Sieve of Eratosthenes.

 

[robert Ihnot]

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

 

[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..

 

[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.

 

[robert Ihnot]

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

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.

 

[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 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

 

[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.

 

[arildno]

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?

 

[Tom McCurdy]

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

 

[devious_]

What about 2?

Well spotted.

 

[krab]

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.

 

[JonF]

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

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

 

[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

 

[alphachapmtl]

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/

 

[chaoseverlasting]

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

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

How is that possible? If f(j) is basically a function of cos²x, it mus lie between 0 and 1. It can't ever go beyond that, that exceeds the range of cos²x .

 

[alphachapmtl]

How is that possible? If f(j) is basically a function of cos²x, it mus lie between 0 and 1. It can't ever go beyond that, that exceeds the range of cos²x .

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

 

[CRGreathouse]

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...

 

[HallsofIvy]

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

$1\le cos^2(x)< 2$
if and only if cos²(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?

 

[alphachapmtl]

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?

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

 

[chaoseverlasting]

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?