python - 如何优化此 Python 脚本，该脚本检查一个数字是否等于其数字总和乘以一个因数？

Question

想深入了解如何优化 Python 脚本的速度。

挑战:“哪些正整数等于其数字和的 23 倍”>> 这是我的功能代码:

def sum_of_digits(number):
    sum = 0;
    for c in number:
        sum += ord(c) - 48;
    
    return sum;

upper_limit = 10000000000;
count = 0;
for i in range(1, upper_limit, 1):
    if(23 * sum_of_digits(str(i)) == i):
        print(i);
        count += 1;

正确地吐出 207 作为答案 (2+0+7 = 9. 9 x 23 = 207)。

问题是执行时间缩放为 (n)。

虽然我可以预先计算 sum_of_digits - 这不会节省时间，我正在寻找 Python 方法来加快执行速度。

我知道我可以深入研究数论并将其“数学化”——但我对我可以从 Python 中榨取什么很感兴趣。

最后，我知道其他语言可能会更快，但我是一名高中物理老师，在暑期类(class)中使用它作为 STEM 示例。

Answer 1

首先，这是 Python，因此您不需要将 ; 放在语句的末尾。由于您正在寻找 23 的倍数的数字，因此如果您遍历 23 的倍数的数字，您可以获得一些性能:

for i in range(0, upper_limit, 23):
    # 'i' will take values 0, 23, 46, ...

如果您处理 int，您的 sum_of_digits 函数会执行得更好。取自here :

def sum_digits(n):
   r = 0
   while n:
       r, n = r + n % 10, n // 10
   return r

所以最终的代码将是:

upper_limit = 10000000000
count = 0
for i in range(0, upper_limit, 23):
    if (23 * sum_digits(i) == i):
        print(i)
        count += 1

print(count)

但是，这仍将在 O(n*m) 中执行，因为您有嵌套循环。

我们可以做一些数学运算并打破循环，而不是试图盲目地找到这样的数字。

For 1 digit numbers 23 * sum_digits(i) would be 23 * 9 = 207 at maximum.
For 2 digit numbers 23 * sum_digits(i) would be 23 * 18 = 414 at maximum.
For 3 digit numbers 23 * sum_digits(i) would be 23 * 27 = 621 at maximum.
For 4 digit numbers 23 * sum_digits(i) would be 23 * 36 = 828 at maximum.
For 5 digit numbers 23 * sum_digits(i) would be 23 * 45 = 1035 at maximum.
.
.
.

You can see the pattern here. We actually don't need to search for the numbers which have 4 digits or more. Because all the 4 digit numbers are greater than 828 and all the 5 digit numbers are greater than 1035 etc. So here is a better solution which breaks when we are sure that all the remaining numbers won't be valid.

def sum_digits(n):
   r = 0
   while n:
       r, n = r + n % 10, n // 10
   return r

upper_limit = 10000000000
count = 0
for i in range(0, upper_limit, 23):
    number_length = len(str(i))
    if number_length * 9 * 23 < i:
        break
    if 23 * sum_digits(i) == i:
        print(i)
        count += 1

print(count)