[Tutor] OverflowError in lucky numbers script

[Dave Angel]

On 01/23/2012 01:20 PM, Alan Gauld wrote:
> On 23/01/12 13:13, Shreesh bhat wrote:
>> I tried optimizing everything all things you guys pointed out and still
>> its orders of magnitude away from the expected result.
>
> That's what I suspected. It means the fundamental approach of testing 
> every number can probably never work.
>
>> Which approach should I follow?
>
> You will need to go back to the math.
> Find a better algorithm than testing all numbers. Maybe
> you can find a way to generate the numbers rather than
> eliminate them?
>
> This may be a problem somebody else has solved so a Google/Wikipedia 
> search may turn up some useful algorithms?
>
> Since it seems to be a homework type assignment it would be normal
> for it to be related to your classwork. So what have you been studying 
> recently that might help?
>
> One thing that might help is to generate all the primes you need in 
> advance? For example if the max number is 10**18 that implies 18 
> digits, so the the max of the squares sum can only be 18*(9*9)=1458. 
> Rather than checking for primeness it might be faster to calculate all 
> primes up to that value and test for inclusion in that set.
> Similarly the primes for addition are max 18*9 = 162, a very small set 
> of primes...
>
> Just a random thought, I have no idea how much that would help, if at 
> all!...
>
I already suggested that, and he already implemented it. Although it was 
inefficient, it was good enough and not the bottleneck.



-- 

DaveA