in reply to Finding Primes

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

Replies are listed 'Best First'.
Re: Finding Primes
by Abigail-II (Bishop) on Aug 14, 2003 at 10:38 UTC
    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

[reply]
[d/l]
[select]
      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]
        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]

In Section Seekers of Perl Wisdom