Find good numbers in a given range This is the Good Numbers problem at Code Chef:


  A number is called a square-free number if there does not exist a number greater than 1, whose square divides the number. For example, 8 is not a square-free number as 4 (the square of 2) divides 8. Similarly, 4 is not a square-free number. However, 1, 3, and 6 are all square-free numbers.
  
  A number \$n\$ is called a good number if the following properties hold:
  
  
  It is a square-free number.
  Let \$s\$ denote the sum of all divisors of \$n\$ (including the trivial divisors 1 and \$n\$). Let \$c\$ denote the number of prime numbers dividing \$s\$. Number \$c\$ should be a prime number.
  
  
  You are given two numbers \$L\$ and \$R\$, and you have to find the sum of divisors (including the trivial divisors) of all the good numbers in the range \$L\$ to \$R\$ inclusive.
  
  Input
  
  The first line of the input contains an integer \$T\$ denoting the number of test cases. The description of \$T\$ test cases follows.
  
  The only line of each test case contains two space separated integers \$L\$ and \$R\$ denoting the range for which you have to find sum of divisors of good numbers.
  
  Output
  
  For each test case, output a single line corresponding to answer of the test case.
  
  Example
  
  Input:

2
1 5
6 10

  
  Output:

6
30

  
  Explanation
  
  
  These numbers in the range 1 to 10 are square-free numbers: 1, 2, 3, 5, 6, 7, 10.
  The sum of their divisors is 1, 3, 4, 6, 12, 8, 18 respectively.
  The number of prime divisors of their sum of divisors is 0, 1, 1, 2, 2, 1, 2 respectively.
  So, the numbers 5, 6, and 10 are good numbers.
  
  
  Example case 1. The only good number in the range 1 to 5 is 5. The sum of divisors of 5 is 6.
  
  Example case 2. In the range 6 to 10, the numbers 6 and 10 are good. The sum of their divisors is 12 + 18 = 30.


How can I improve my code? It is taking too much time to execute (5–20 seconds). Where the time limit is 1 second.

My code:


finds square free integers,
gets the sum of the unique divisors of the number,
Finds the amount of prime divisors for (2).




import time
start_time = time.time()
n=int(input())

for t in range(n):
 v=[]  
 a,b=[int (x) for x in input().strip().split(' ')]
 for u in range(a,b+1):
        if u==1:
            v.append(u)
        elif u&gt;1:
            for k in range(2,u):               # to find the square free no's
                if(u%(k**2)==0 and u&gt;=(k**2)):

                    break;
            else:

                    v.append(u)
 sd=[]
 pd=[]
 for j in v:
    s=0

    for k in range(1,j+1):
        if j%k==0:
            s=s+k   #gives the no. of divisor for each square free no
    sd.append(s)

 for k in sd:  #This part is for finding the no of prime divisors for each square free no.
  count=[]
  for x in range (1,k):
   for u in range(2,x):
      if x%u==0 :
          break
   else :

       if (x!=1 and k%x==0):
         count.append(x)

  pd.append(len(count))  #counts the no of prime divisor


 pos=0
 su=0
 for j in pd:

    if j&lt;=1:
      pos=pos+1
    else:

      su=su+sd[pos]
      pos=pos+1
 print(su)      #prints the sum of divisor of good numbers
print("---%s seconds ---" % (time.time() - start_time))
for k in sd:
    count = []
    for x in range(1, k):
        for u in range(2, x):
            if x % u == 0:
                break
        else:
            if x != 1 and k % x == 0:
                count.append(x)
    pd.append(len(count))


This part of the code is very slow. You are finding prime numers u through trial division, which is a very naïve method.

Basically, any code that involves prime numbers is going to be extremely slow if you don’t use a “smart” algorithm. Sieves are a good place to look. If I replace your code with

from sympy.ntheory.factor_ import primefactors
for k in sd:
    pd.append(len(primefactors(k)))


it is fifty times faster for the test input

1
1 500


(0.02 sec instead of roughly a second).



A final note: profiling is a very useful technique for finding out which steps of your code take a long time. Your code is impossible to profile if you don’t split it up into smaller functions, so please do that.