如何加速我的代码：只找到五个奇数分隔符。偶数分频器的数量没有限制

Question

我需要找到范围 (45 000 000, 50 000 000 +1) 内的所有数字，它们只有五个奇数分隔符。偶数分频器的数量没有限制。这里我的代码太慢了

listN=[]
for i in range (45000000,50000000+1):
    sqrtI=i**0.5
    counter=0
    sqrtI=int(sqrtI)
        
    for j in range (1,sqrtI+1):
        divj,modj=divmod(i,j)
        if modj==0:
            if j%2==1:
                counter+=1
            if divj%2==1:
                counter+=1
        if counter >5:
            break
    if counter==5:
        listN.append(i)
    
        
    if i%100000==0: # 
        print(i)
        
print(listN)

Answer 1

取奇数n。如果这个奇数n有一个奇数约数m，那么n/m也是一个奇数。但这意味着奇数成对出现，m 和 n/m。数字 n 可以有 5 个奇数的唯一方法是如果某对实际上具有相同的数字，即 m = n/m。但这意味着 n = m*m，即 n 必须是奇数的平方。因此，您无需检查范围内的所有奇数，只需检查奇数的平方即可。

现在考虑一个偶数 n。让我们将这个数字除以 2，直到我们得到一个奇数 m（例如，从 n=40 我们得到 40 -> 20 -> 10 -> 5，所以 m = 5）。 m 的任何奇数除数也将是 n 的奇数除数，反之亦然。因此，n 和 m 具有相同数量的奇数除数。所以，正如我们在上面看到的，数字 m 必须是奇数的平方。这意味着，n 必须是奇数的平方乘以 2 的某个幂。这意味着您不需要检查范围内的每个偶数，只检查那些奇数的平方乘以 2 的某个次方。

更新

下面是示例实现：

def method1(a, b):
    result = []
    for n in range(a, b + 1):
        m = n
        while (m > 1) and (m % 2 == 0):
            m /= 2  
  
        root = int(m ** 0.5 + 0.5)
        if root * root != m:
            continue    

        count = 0
        for i in range (3, root):
            if (i % 2 == 0) or (m % i != 0):
                continue
            count += 1
            if count > 1:
                break
    
        if count == 1:
            result.append(n)    
    return result

def generate_primes(start, end):
    result = []
    for n in range(start, end + 1):
        if n % 2 == 0:
             continue
        root = int(n ** 0.5 + 0.5)
        for i in range(3, root + 1):
             if n % i == 0:
                 break
        else:
            result.append(n)
    return result

def method2(a, b):
    result = []
    primes = generate_primes(3, int(b ** 0.25 + 0.5))   
    for p in primes:
        n = p**4
        while n < a:
            n *= 2
        while n <= b:
            result.append(n)
            n *= 2
    return sorted(result)
        
a = 45000000
b = 50000000

print(method1(a, b))
print(method2(a, b))

第一个 method1 使用上述方法。第二个 method2 使用更高级的方法，速度大约快 100 倍。第二种方法的思想是生成区间上界的 3 和四次方根之间的所有素数（在我们的例子中是 50000000，所以素数不能大于 84）。然后我们计算所有这些质数的 4 次方并尝试将它们乘以 2 直到我们进入所需的区间内。两种方法产生相同的输出

[45212176, 45265984, 47458321, 48469444]

下面是方法 2 有效的长证明：

要了解方法 2 的工作原理，我们需要继续分析方法 1。我们知道，为了有 5 个除数，我们的数字 n 必须等于奇数的平方乘以二的幂：

n = m*m * (some power of 2)

其中 m 是奇数。数字 m*m 必须恰好有 5 个奇数约数。但是，我们已经知道其中的 3 个：1、m 和 m*m。因此，m*m 应该只存在 2 个奇数约数，其中只有一个在 1 和 m 之间。让我们将第一个奇数除数表示为 p（它应该在 1 和 m 之间）。那么第二个奇数除数就是m*m/p。数字 p 必须是质数。如果不是，则 p 的任何约数也将是 m*m 的约数。我们知道第二个约数是m*m/p，所以m*m一定能被p整除。但是因为 p 是质数 m 也应该被 p 整除： m = p*x，其中 x 是某个（奇数）数。但是，如果 x 不等于 p，那么我们就找到了另一个介于 1 和 m 之间的数 x，它是 m*m 的约数。这是不可能的，所以 x 必须等于 p 和 m = p*p。因此，我们已经证明 m*m = p^4，即我们的数字 n 必须是质数的四次方乘以 2 的某个次方。

如何加速我的代码：只找到五个奇数分隔符。偶数分频器的数量没有限制

How to speed up my code : find five odd dividers only. The number of even dividers is no limit

python

integer-division