Hi On 23 January 2012 22:55, Steven D'Aprano <st...@pearwood.info> wrote: > > > > >Can i work around that way in python or should i come up with a new > > >algorithm? > > > > You definitely need a fundamentally different algorithm. > > I expect that this is some question from one of those annoying > websites that offer extremely advanced mathematics puzzles disguised as > a programming challenge. (Well I find them annoying. The answer almost > always turns out to be something which took a genius of the level of > Euler or Gauss to discover, and they expect you to come up with the > answer on your own.) >
The OP previously posted the question, and having reread it I think perhaps he's too fixated on the maximum possible range in the spec/question which gives rise to an practically impossible computational burden. To be precise, I think trying to feed A=1 and B=10^18 seems to me to be asinine given that the the example test cases given in the problem statement uses values of A and B that are a) relatively small and b) quite close together. That therefore gives me the impression that being able to calculate all the answers for the whole 1...10^18 range is rather not expected. (The very fact that you need to specify a sub-range within which to calculate the lucky numbers in, implies that it's not expected, actually.) Anyway, for reference I post the original question again: > *Lucky Numbers* > A number is called lucky if the sum of its digits, as well as the sum of > the squares of its digits is a prime number. How many numbers between A > and B are lucky? > Input: > The first line contains the number of test cases T. Each of the next T > lines contains two integers, A and B. > Output: > Output T lines, one for each case containing the required answer for the > corresponding case. > > Constraints: > 1 <= T <= 10000 > 1 <= A <= B <= 10^18 > Sample Input: > 2 > 1 20 > 120 130 > Sample Output: > 4 > 1 > Explanation: > For the first case, the lucky numbers are 11, 12, 14, 16. > For the second case, the only lucky number is 120. Walter _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
