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

[Alan Gauld]

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