Dec 2015
1 / 2
Dec 2015
Dec 2015
jamesjohn1097
Dec '15
1 
  from math import sqrt as sq
  import sys

  is_knumber = {}
  knumber_count = []

  def is_prime(x):
     if (x < 2 ) : return False
     for i in range(2,int(sq(x))+1):
        if x % i == 0:
            return False
   return True


  def calculateSumOfDivisors():
     is_knumber[2] = True
     for i in range(2,1001):
          if is_prime(i):
               pwr = i*i
               sod = 1+i+i*i
               while(pwr < 1000001):
                    if(is_prime(sod)):
                        is_knumber[pwr] = True
                    pwr *= i
                   sod += pwr


knumber_count.append(0)
for i in range(1,1000001):
    knumber_count.append(knumber_count[i-1] + int(is_knumber.get(i,False)))

return knumber_count

  if __name__=='__main__':
      result = []
      calculateSumOfDivisors()
      t = int(input())
      while (t):
          t1,t2 = input().split()
          result.append(knumber_count[int(t2)]-knumber_count[int(t1)-1])
          t -= 1

      for i in result:
          print(i)

I dono how to optimize the above solution in python, can someone please help me !!! `

  • created

    Dec '15

  • last reply

    Dec '15
  • 1

    reply

  • 814

    views

  • 2

    users

daft_wullie
Dec '15

The indentation of your code appears to be broken. Please correct your post - or did you use tabs? And there is strange code on module level just before the 

if __name__ ...

idiom.
To get an idea where the bottleneck is, you can use the Python profiler in the standard library.