[Tutor] OverflowError: cannot fit 'long' into an index-sized integer

[Keith Winston]

oops, I'm sorry I didn't realize Danny's message to me was private, but
you're right that's better than publishing this right out.

Also: although the sqrt(n) algorithm worked to solve the problem, it isn't
actually correct. There are cases in which it will fail, many in fact.
Oops. One would need to take the Sieve all the way up to n/m for it to work
in this simple version, where m is the lowest prime factor of the number
(which this algorithm WILL always find). There's a nice recursive version
in there somewhere.

Keith



On Tue, Jan 7, 2014 at 7:17 PM, Alan Gauld <alan.gauld at btinternet.com>wrote:

> On 07/01/14 21:22, Keith Winston wrote:
>
>  Note that his code doesn't really (need to) create a sieve of
>> Eratosthenes all the way to n, but only to sqrt(n). It then tests for
>> divisibility.
>>
>
> I'm not sure what you mean here.
> His algorithm was using an array of booleans to indicate whether a number
> was prime. How does building a list up to sqrt(n) identify primes above
> sqrt(n)?
>
> For example if n is 100 how do you detect that 97 is prime
> if you only build a sieve up to 10?
>
> I know you can find the highest prime factor without finding all the
> primes themselves but that's exactly the kind of alternative algorithm
> Euler is looking for. But then it's no longer using Jorge's algorithm,
> which is to test all numbers for primeness then find the highest one that
> is a factor of n, is it?
>
> Ah, OK a light bulb just went on. Amazing what happens when you start
> typing your thoughts! What you mean is to build a seive to identify all
> primes up to sqrt(n) and then test those primes as factors. I had thought
> you intended testing *all* numbers up to sqrt(n) then seeing if they were
> prime. Quite different...
>
> As you say, it's maybe a matter of defining 'tuning' versus creating
> an entirely new algorithm! ;-)
>
>
> --
> Alan G
> Author of the Learn to Program web site
> http://www.alan-g.me.uk/
> http://www.flickr.com/photos/alangauldphotos
>
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> To unsubscribe or change subscription options:
> https://mail.python.org/mailman/listinfo/tutor
>



-- 
Keith
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20140107/d327983e/attachment.html>