in reply to Finding Primes

Any two 200 digit primes will do it, but your isa_prime() and gen_primes() subs are way too inefficient to find primes of that size. You are hoping to test primality by exhaustively checking every number less than the candidate as a divisor. That will take more than 10**200 divisions. If you can do one every 10 nanoseconds, that gives you 10**192 seconds, or around 10**175 ages of the universe to check a single number.

Has your math professor given you some reading on the subject of primality testing? If not, check The Prime Pages.

Math::Pari is very good for number theory kind of things.

After Compline,
Zaxo

Replies are listed 'Best First'.
Re: Re: Finding Primes
by sauoq (Abbot) on Aug 14, 2003 at 02:38 UTC
    Any two 200 digit primes will do it

    Without knowing all the 200 digit primes, I can't say whether or not that is a true statement. I wouldn't assume it is sufficient, however. The square root of 10^399 is a little greater than this 200 digit number: 

    3162277660168379331998893544432718533719555139325216826857504852792594
+438639238221344248108379300295187347284152840055148548856030453880014
+6905195967001539033449216571792599406591501534741133394841240

    [download]
    So, if there are two primes between 10^199 and that number, then there will be two 200 digit primes whose product is not a 400 digit number.

    -sauoq
"My two cents aren't worth a dime.";
[reply]
[d/l]
      First of all, there are an infinite number of primes and there is a theorem by Bertrand which states that there is a prime between any natural number n and 2*n. So there are two prime numbers which product is a 400 digit number.
[reply]

        Very good, but why are you replying to me? I was arguing that the product of two 200 digit primes is not necessarily 400 digits. It may only be 399. Perhaps you'd like to tell the OP that he can prove the existence of such primes without finding them. I expect that was what his professor had in mind anyway...

        -sauoq
"My two cents aren't worth a dime.";
[reply]
      Well, as 10^1 is a 2 digit number, 10^399 is a 400 digit number....:)

      thor

[reply]
      A reply falls below the community's threshold of quality. You may see it by logging in.
Re: Re: Finding Primes
by Tommy (Chaplain) on Aug 14, 2003 at 02:00 UTC
    If you can do one every 10 nanoseconds, That gives you 10**192 seconds, or around 10**175 ages of the universe. That to check a single number.

    Yikes! And you know my professor said that the smallest possible starting point would be two numbers of 10**200. At least this is what I gathered from our conversation. Is that right?

    Math::Pari is very good for number theory kind of things.

    I'll have a look at that when I get home from school here. Thanks for the tip.

    I'm still pretty lost here. I don't know where to start.

    Tommy Butler, a.k.a. TOMMY
[reply]

In Section Seekers of Perl Wisdom