Re: Finding Primes

[Foggy Bottoms]

There are a lot of algorithms out there to help you deal with prime numbers. Here are a couple ordered by efficiency, the first being the most efficient. If you run the code in C, you'll notice there's a sharp drop in time consumption between the first and 3rd examples but that the change is very slight between the 3rd and 4th...
$n is the number we're trying to figure out whether it's prime or not...

• divide $n by all the numbers preceding it until you find a multiple of $n or until you run out of numbers
• Same method as above, but instead of going all the way to $n, you can solely consider all the numbers till 1+trunc(sqrt($n))...
• Same method as above but exclude all the pair numbers (easily done by having a loop where the index is increased twice)
• Same method as above plus store all the previous prime numbers you've already found and exclude their product...

[Abigail-II]

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

[Foggy Bottoms]

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

[Abigail-II]

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