如何足够快地计算减少适当分数的数量？

Question

我目前正在解决一个数学问题,其中我需要计算减少的适当分数的数量,分子和分母都超过1000000(10 ^ 6).

我有适用于小数字的代码; 给出的示例(值= 8)给出正确的(给定的)答案21.

但是由于我不知道的原因,这个代码似乎对大数字来说非常慢.我在SO上阅读了大量类似的问题,但找不到任何有用的东西.我仔细研究了这个和这个,但这并没有真正帮助我.我的代码以可接受的速度运行,直到1000,然后它变得超级超慢.

import math

def is_prime(n):
    if n == 2:
        return True
    if n % 2 == 0 or n <= 1:
        return False
    sqr = int(math.sqrt(n)) + 1
    for divisor in range(3, sqr, 2):
        if n % divisor == 0:
            return False
    return True

def get_divisors(n):
    liste = [1]
    if n % 2 == 0:
        liste.append(2)
    for divisor in range(3, n+1):
        if n % divisor == 0:
            liste.append(divisor)
    return liste

def intersect(a, b):
    return list(set(a) & set(b))

until = 1000

primes = list()
for i in range(int(until)):
    if i != 1 and i != 0:
        if is_prime(i):
            primes.append(i)

pos = 0
for i in range(1, until+1):
    if i%50 == 0:
        print(i)
    if is_prime(i):
        pos += (i-1)
    else:
        di = get_divisors(i)
        di.remove(1)
        for j in range(1, i):
            dj = get_divisors(j)
            if intersect(di, dj)==[]:
                pos+=1   


print(pos)

我想知道我的程序的哪些部分正在降低速度以及如何解决这些问题.

Answer 1

如果素数本身足够快（我仍然推荐埃拉托色尼筛，它比你可以进行大量生成素数的素数测试更好），则除数的生成不会

for divisor in range(3, n+1):
    if n % divisor == 0:
        liste.append(divisor)

当这个循环O(n)可能具有O(n**0.5)如下复杂性时，它就具有复杂性：

liste = set()  # okay, the var name isn't optimal now :)
for divisor in range(3, int((n+1)**0.5)+1):
    if n % divisor == 0:
        other = n // divisor
        liste.add(divisor)
        liste.add(other)

当您找到“低”（<= sqrt(n)）除数时，other它只是互补的“高”除数。这使得循环变得更短。

既然您要通过转换为 a 来执行交集set，为什么不set首先创建 a 呢？优点是，在完美的正方形中，您不会两次添加相同的值（您可以测试，但不确定它会更快，因为碰撞很少见）

现在一切都是set这样：

if intersect(di, dj)==[]:
            pos+=1   

变成：

if not di.isdisjoint(dj):
   pos += 1

• set每次迭代都没有创建
• 没有set创造知道这些集合是否具有共同的值。只需使用set.isdisjoint

最后一件事：如评论中所述，在主循环中测试素数时，您将is_prime()再次调用，而不是将生成的素数存储在 a 中set并进行测试in。