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
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
