Re: Finding Primes

None of them are at all feasible when trying to determine the primeness of a 200 digit number. The square root of a 200 digit number is a 100 digit number. Even if the first 200 digit number you are going to try is prime, and take your last suggestion, you'd need to keep track of all the prime numbers less than 100 digits long.

Considering there are about n / ln n prime numbers less than n, you'd need to keep track of about 4 * 10**98 prime numbers.

Many people in this thread just don't seem to realize how big a 200 digit number is.

Abigail

Comment on Re: Finding Primes Select or Download Code

Replies are listed 'Best First'.
Re: Re: Finding Primes by Foggy Bottoms (Monk) on Aug 14, 2003 at 10:52 UTC
Hi Abigail, You're quite right but I never actually meant to give a solution to the 200-digit long number, I was only recapping the typical algorithms one can come up with, pretenselessly ;-)... There must be an option with n! numbers because they grow so quickly - I thought that n!+1 might a prime number but an easy counter-example is n=4 (which'd give n!=24 hence n!+1=25 = 5*5, barely what you can call a prime number...)	[reply]
Re: Finding Primes by Abigail-II (Bishop) on Aug 14, 2003 at 11:03 UTC
The only thing you can say about `n! + 1` is that it will only contain prime factors that are larger than `n`. And that the series `(n! + 2) .. (n! + n)` will not contain a prime number. Abigail	[reply]
Re: Re: Finding Primes : Fermat's "small" theorem by Foggy Bottoms (Monk) on Aug 14, 2003 at 13:17 UTC
The following theorem might help : Fermat, a French mathematician, once proved that : " If p is a prime number whilst GCD(p,a)==1 then a^p-1 is congruous to 1 modulo p." But actually this theorem isn't enough, it helps you prove a number is not prime, not the other way round... Lucas, another French dude, came up with yet another theorem which looks for Mersenne's prime numbers : Given p an odd number, the number M=2^p-1 is prime if and only if 2^p-1 divides S(p-1) where S(n+1)=S(n)² - 2, and S(1) = 4. Further down the road, Indian scientists came up with a very interesting paper you may want to check out : they probably have an answer to your problem : <a href=http://www.cse.iitk.ac.in/news/primality.pdf>primality.pdf</a>... Hopefully, I've been of some help - maths are really interesting and I always enjoy digging into them...	[reply]