[Tutor] OverflowError in lucky numbers script
Alan Gauld
alan.gauld at btinternet.com
Mon Jan 23 19:20:15 CET 2012
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!...
--
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
More information about the Tutor
mailing list