[Tutor] OverflowError in lucky numbers script

[Dave Angel]

On 01/22/2012 06:37 AM, Shreesh bhat wrote:
> I m using Python 2.7
> Steven wrote:
> " Scale your numbers from time to time, to avoid them getting too big"
> What does this mean?
>
> inp refers to the sample input test case I have given at first.Its a string
> containing two numbers,
> The program has to handle large numbers till 10**18 and also has to execute
> considerably fast (within 16 CPU time).
>
> Using xrange() causes the OveflowError,Whereas using range() causes too
> many items
> Is writing my own generator only solution? Or is there another way in which
> i can generate big numbers and in considerably fast manner?
Without knowing any constraints on the range (other than the limits are 
each less than 10**18), you either have to write your own generator or 
do a while loop.   That's not your problem.  Write one of them, and make 
sure your program now gets correct answers.

Now you're apparently adding a new constraint "execute considerably fast 
(within 16 CPU time)".  No idea what that means, but perhaps you left 
out the unit.  Do you mean 16 minutes?

When a program is correct, but too slow, you may need faster functions 
(like xrange is usually faster than range, and both are faster than one 
your wrote by hand).  Or you may need a better algorithm.

For each individual number, I think you would find that the bulk of the 
time is spent checking isprime().  There are functions that are much 
faster than the way you're doing, but I expect the time problem doesn't 
occur till you're checking lots of such numbers.

When you have slow functions called lots of times, you can either speed 
up the function, or reduce the number of times its called.

What I would do is figure out what the largest sum might be (9 * 19, 
more or less).  Calculate the isprime(n) and isprime(n*n) for each of 
those, and save them in a table.  Now your main loop can just sum the 
digits and consult the table.  If that's not fast enough, optimize the 
way you sum the digits.


-- 

DaveA