How can I optimize the code to run at a minimal time while still using the CPython implementation?
def detdivisors(n):
"""This function tests if the sum of the divisors of a given
a number is a perfect square and returns the sum if it is, and
false if it is not"""
import math
divisors = []
sum = 0
for i in range(1,n+1):
if n%i == 0:
divisors.append(i)
for i in range(0, len(divisors)):
sum = sum + (divisors[i]**2)
if (math.sqrt(sum)%1 == 0):
return sum
else:
return False
def list_squared(m, n):
"""This function runs for the previous function and returns a
list that has all the numbers that satisfy the condition and
their associated sums. """
answers = []
for i in range(m, n+1):
ans = []
if detdivisors(i) != False:
ans.append(i)
ans.append(detdivisors(i))
answers.append(ans)
return answers
num = int(input("Enter the beginning: "))
end = int(input("Enter the end: "))
ans = list_squared(num,end)
print(ans)
**I am trying to optimize the code by putting every thing in a single function to reduce the number of function calls, but it is still not giving me the kinds of speed I really want to get. **
Here is some pure-Python code that does what you want fairly quickly. This gains speed in mutliple ways. First, it uses a mathematical way to calculate the sum of the divisors of a number, using only the prime decomposition (product of powers of distinct primes) of the number. Second, it uses a previously-calculated list of prime numbers to speed up the prime decomposition. So this code has longer code and uses more memory but is faster. Third, I used Python's built-in is_integer function to speed up detection of perfect squares. Last, I removed the error-checking from my code to speed it up. This code works up to the prime number greater than the square of the last number in the prime list. You said in a comment that you need numbers up to one thousand. I increased that to one million, just to be sure, and that takes 168 prime numbers. (If you are sure that you will never need to go above 1000 you can use the first 11 prime numbers, up to 31.)
I just ran %timeit on my code, and it takes 3.26 milliseconds to calculate and print the resulting list up to 1000. It takes 9.05 seconds to do that for one million. Do you need anything faster?
import math
primelist = [
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
947, 953, 967, 971, 977, 983, 991, 997]
def sumdivisors(n):
"""Return the sum of the positive divisors of n. This is guaranteed
to work if 0 < n < 1000000 and will work for many larger numbers.
"""
sqrtn = int(math.sqrt(n))
result = 1
for p in primelist:
if p > sqrtn:
break
exponentofp = 0
while n % p == 0:
n //= p
exponentofp += 1
if exponentofp:
sqrtn = int(math.sqrt(n))
result *= (p**(exponentofp + 1) - 1) // (p - 1)
if n > 1:
result *= n + 1
return result
num = int(input("Enter the beginning: "))
end = int(input("Enter the end: "))
ans = [n for n in range(num, end+1) if math.sqrt(sumdivisors(n)).is_integer()]
print(ans)