有没有一种方法可以优化此代码以查找数字的除数？

Question

我已经在Julia中编写了一个程序，可以有效地计算数字n的除数。该算法是原始的（据我所知），并且是基于Sieve of Eratosthenes的。它基本上是这样的：

对于给定的素数p，令p^k || n;列表中的每个数字m删除满足p^{k+1} | m的条件，并重复此过程每个素数p < n。

素数是使用传统的Eratosthenes筛子原位计算的。

function ν(p, n)     #returns the smallest power of p that does not divide n
    q = 1

    for i = 0:n
        if mod(n, q) != 0
            return (i, q) 
        end

        q *= p
    end
end

function divisors(n)    #returns a list of divisors of n
    dsieve, psieve = BitArray([true for i = 1:n]), BitArray([true for i = 1:n])
    psieve[1] = false

    for i = 1:n
        if psieve[i] && dsieve[i]
            #sieving out the non-primes
            for j = i^2:i:n
                psieve[j] = false
            end

            #sieving out the non-divisors
            v = ν(i, n)[2]
            for j = v:v:n
                dsieve[j] = false
            end
        end
    end
    return dsieve #the code for converting this BitArray to an array of divisors has been omitted for clarity
end

虽然这可以很好地工作，但我发现同时使用两个筛网效率低下。我认为可以通过允许筛子数组中的每个元素采用三个不同的值（对应于unchecked，divisor和not divisor）来解决此问题，但是之后就不能再实现为BitArray 。

我也尝试过修改函数ν以提高效率：

function ν₀(p, n)      #the same as ν, but implemented differently
    q = p
    while mod(n, q) == 0
        q = q^2
    end

    q = floor(Int64, √q)
    q < p ? 1 : q * ν₀(p, n÷q)    #change 1 to p to get the smallest power of p that does not divide n
end

尽管虽然更复杂，但是比以前的算法要快一些-特别是当p除以​​n的幂很大时。

Note：我知道找到数字除数的算法要好得多。我很好奇，可以在多大程度上优化上述算法。正如我前面提到的，使用两个筛子相当麻烦，并且找到一种消除质数的传统筛子而不影响效率的方法将是一个很好的选择。

Answer 1

我可以指出几件事-

dsieve, psieve = BitArray([true for i = 1:n]), BitArray([true for i = 1:n])

为每个数组分配两次（列表comp，然后进行转换）。这样就可以了：

dsieve = trues(n)
psieve = trues(n)

接下来，我们可以确保通过使用任何类型的更快的索引

for i in eachindex(psieve)

而不是手动范围。然后，您可以在循环前加上

@inbounds for i in eachindex(psieve)

或者走得更远，如果您使用的是Julia 1.3或更高版本，并对其进行多线程处理（假设您在运行JULIA_NUM_THREADS之前已设置好它]

@inbounds Threads.@threads for i in eachindex(psieve)