Prime testing [was Re: My backwards logic]

2014-09-06 Thread Steven D'Aprano
Denis McMahon wrote: > Note also that when searching for factors of a number n, and starting at > 2, you can generally stop at somewhere around n/3, The largest factor of N you actually need to check is sqrt(n). Every factor of n below the square root has a corresponding factor above it, e.g. if

Re: Prime testing [was Re: My backwards logic]

2014-09-06 Thread Chris Angelico
On Sat, Sep 6, 2014 at 8:38 PM, Steven D'Aprano wrote: > 3, 5, 7, 9 is a waste of time, 11, 13, 15 is a waste of time, ... I love this sequence. ChrisA -- https://mail.python.org/mailman/listinfo/python-list

Re: Prime testing [was Re: My backwards logic]

2014-09-06 Thread Manolo Martínez
On 09/06/14 at 08:38pm, Steven D'Aprano wrote: > But even that's not how the specialists do it. If you want to check whether > (say) 2**3000+1 is prime, you don't want to use trial division at all... When I was interested in these things, specialists would use the [number field sieve](https://en.w

Re: Prime testing [was Re: My backwards logic]

2014-09-07 Thread Peter Pearson
On Sat, 6 Sep 2014 12:53:16 +0200, Manolo Martínez wrote: > On 09/06/14 at 08:38pm, Steven D'Aprano wrote: >> But even that's not how the specialists do it. If you want to check whether >> (say) 2**3000+1 is prime, you don't want to use trial division at all... > > When I was interested in these th

Re: Prime testing [was Re: My backwards logic]

2014-09-07 Thread Manolo Martínez
On 09/07/14 at 06:53pm, Peter Pearson wrote: > On Sat, 6 Sep 2014 12:53:16 +0200, Manolo Martínez wrote: > > On 09/06/14 at 08:38pm, Steven D'Aprano wrote: > >> But even that's not how the specialists do it. If you want to check whether > >> (say) 2**3000+1 is prime, you don't want to use trial div

Re: Prime testing [was Re: My backwards logic]

2014-09-07 Thread Dan Stromberg
On Sun, Sep 7, 2014 at 11:53 AM, Peter Pearson wrote: > On Sat, 6 Sep 2014 12:53:16 +0200, Manolo Martínez wrote: >> On 09/06/14 at 08:38pm, Steven D'Aprano wrote: >>> But even that's not how the specialists do it. If you want to check whether >>> (say) 2**3000+1 is prime, you don't want to use tr