Path: csiph.com!news.swapon.de!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups: comp.programming
Subject: Re: really? (lame question about primes)
Date: Tue, 01 Sep 2015 15:48:19 +0100
Organization: A noiseless patient Spider
Lines: 31
Message-ID: <87y4gqmc0c.fsf@bsb.me.uk>
References: <5e5de47a-7353-4ffc-9f5d-ec083d1d63ba@googlegroups.com> <kt4Fx.394338$3n4.170027@fx35.am4> <44a165dc-8447-4ae0-8695-557a7ddf00cf@googlegroups.com> <ms3peh$o5v$1@dont-email.me> <_RfFx.418341$bt.398932@fx32.am4>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: mx02.eternal-september.org; posting-host="017616aa25f81ec581c44d76d61ba2f3"; logging-data="9424"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19KnUqseFwUGr54KhsOcxLlt9NYxyD0Ws0="
Cancel-Lock: sha1:42/oyEodJXNrJMvKUUEBlIOFcGM= sha1:/xx8kBi7TY5nBRnd9YXiW3WBehI=
X-BSB-Auth: 1.c386e21e7bef98b9b052.20150901154819BST.87y4gqmc0c.fsf@bsb.me.uk
Xref: csiph.com comp.programming:5686

Richard Heathfield <rjh@cpax.org.uk> writes:

> On 01/09/2015 10:01, David Brown wrote:
>
> <snip>
>
>> Yes, you can factorise C by trying to multiply pairs A * B and see if
>> they match.  The trouble is, with a 600 digit number there are quite a
>> lot of such pairs to try!
>
> Well, there aren't all that many really, and the OP specified two
> 300-digit integers, so we needn't bother with lower numbers.
>
> There are only 9*10^299 300-digit numbers, so we need to test
> 81*10^598 = 8.1*10^599 pairs.

Although that's not fir's suggested algorithm.  He suggests testing only
primes as divisors and he might think that large primes are "rare" (many
people do).

The prime number theorem gives a lower bound (for x > 10) of x/log(x)
for the number of primes less than x, so it's not hard to see that
testing prime divisors alone won't help the calculations very much (and
may make matters worse by having to make them in the first place).

(Yes, I know you were mainly being humorous, but if someone thinks that
there are very few large primes the joke would be pointless.)

<snip>
-- 
Ben.