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

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.

StackExchange Code Review Q#151764, answer score: 7