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