Re: really? (lame question about primes)

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.programming
Subject	Re: really? (lame question about primes)
Date	2015-09-01 15:48 +0100
Organization	A noiseless patient Spider
Message-ID	<87y4gqmc0c.fsf@bsb.me.uk> (permalink)
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>

Show all headers | View raw

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.

Thread

really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-08-31 12:07 -0700
  Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-08-31 23:23 +0100
    Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 01:18 -0700
      Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-01 11:01 +0200
        Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-01 12:20 +0100
          Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-01 15:48 +0100
            Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 13:26 -0700
              Re: really? (lame question about primes) Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 02:12 -0500
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 08:38 +0100
                Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 14:03 +0200
          Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 13:24 -0700
            Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-01 22:27 +0100
              Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 15:02 -0700
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-01 23:20 +0100
                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 01:22 +0200
                Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 17:18 -0700
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 02:19 +0100
                Re: really? (lame question about primes) James Dow Allen <gmail@jamesdowallen.nospam> - 2015-09-02 12:42 +0000
                Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-02 14:21 +0100
                Re: really? (lame question about primes) Johannes Bauer <dfnsonfsduifb@gmx.de> - 2015-09-02 17:45 +0200
                Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-02 18:06 +0100
                Re: really? (lame question about primes) James Dow Allen <jdallen2000@yahoo.com> - 2015-09-03 17:05 -0700
                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-04 02:18 +0200
                Re: really? (lame question about primes) Chad <cdalten@gmail.com> - 2015-09-03 22:37 -0700
                Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-03 23:49 -0700
                Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-04 00:18 -0700
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-04 08:25 +0100
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 14:36 +0100
                Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-02 16:49 +0100
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 17:32 +0100
            Re: really? (lame question about primes) Kaz Kylheku <kaz@kylheku.com> - 2015-09-01 22:55 +0000
              Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 01:15 +0200
          Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 03:19 +0200
            Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 02:37 +0100
              Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 11:24 +0200
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 10:42 +0100
                Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-02 03:01 -0700
                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 12:28 +0200
                Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 14:12 +0200
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 13:19 +0100
                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 14:56 +0200
                Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 15:47 +0200
                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 16:27 +0200
                Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 16:37 +0200
                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 17:01 +0200
                Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-03 10:55 +0200
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-03 10:05 +0100
                Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-03 11:49 +0200
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-03 10:54 +0100
                Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-03 13:22 +0200
                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-03 13:58 +0200
                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 13:34 +0100
  Re: really? (lame question about primes) Robert Wessel <robertwessel2@yahoo.com> - 2015-08-31 23:10 -0500

csiph-web