[Tutor] OverflowError in lucky numbers script

[Alan Gauld]

On 23/01/12 06:10, Shreesh bhat wrote:
>
> def sieve(maxi):
>    primes = range(2,maxi+1)

You can reduce the size of primes by only storing the odd numbers.
range takes a third parameter that sets the stepsize, you cxan
use that to skip evens...

>    for i in primes:
>      j = 2

you can then start here with j=3...

>      while i * j <= primes[-1]:
>        if i * j in primes:
>          primes.remove(i*j)

I'm not sure which is faster but I suspect list comprehensions
could be used here too at the expense of consuming more memory.

primes = [num for num in primes if i*j in primes]

but the while loop stops earlier so it's hard to be sure which
is more efficient unless you try it.

>        j += 1
>    return primes
>
> maxi=(10**2)*18   #Generating the table till the largest possible prime
> tab=sieve(maxi)
> table={}
> for i in tab:
>      table[i]=0
>
> def isprime(n):
>      return table.has_key(n)
>
> count=0
>
> def islucky(n):   # modified islucky function
>    global count
>    sum1=0
>    sum2=0
>    for letter in str(n):
>      tmp=ord(letter)-48
>      sum1+=tmp
>      sum2+=tmp**2

>    if isprime(sum1):
>      if isprime(sum2):
>        count+=1

This last should be marginally faster if you use an and test:

     if isprime(sum1) and isprime(sum2):
         count+=1

> number=raw_input()  # Number of test cases.Its constraint (1,10000)

Put the description as the prompt - make life easier for your user, even 
if it is only you! Learn good habits early.

number=raw_input("Number of test cases(1-10000).")


> def execute():
>    global count
>    for i in range(int(number)):
>        inp=raw_input()    # startnumber and endnumber pair. Its
> constraint (1,10**18)

Same here:

inp=raw_input("startnumber and endnumber pair(1-10**18)")

>        a=inp.split()
>        startnum=int(a[0])
>        endnum=int(a[1])
>        count=0
>        while startnum != endnum:

!= is a risky strategy, it can lead to accidental infinite loops. Better 
to use

while startnum < endnum:

and while we are at it, do you really mean not to test endnum?

>            islucky(startnum)
>            startnum+=1
>        print count
>
> execute()
>
> The program is executing correctly but it has to execute 16 seconds for
> the constraints.

So how close are you? That gives us a clue on how much farther we need 
to optimise...

HTH
-- 
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/