（相对）快速找到小于 10 000 000 的数的除数

Question

假设我所说的一切都是小于 1000 万的自然数。

我希望为所有小于 10 000 000 的数字预先生成最低素因数 (LPD) 列表。例如，LPD(14) == 2，LPD(15) == 3，并且任何素数的 LPD 都是它本身。

我已经预先生成了所有的素数。访问第 n 个素数是一个简单的数组查找。效率为：O(1)

我已经预先生成了一个查找 table 来确定给定数字是否为质数。访问第 n 个素数是一个简单的数组查找。效率为：O(1)

现在，我计算给定数字的 LPD 的天真算法是遍历所有素数，直到一个素数除以该数字。但这需要很长时间。我可以用一半的时间生成所有小于 1000 万的质数，而找到所有数字的最小除数所需的时间只有一半（使用我不明白的阿特金筛法，但它是从伪代码实现的）。

有没有更好的计算最低素因数的算法？

Answer 1

实际上不确定为什么您期望对几乎相同的问题有更高的性能。

筛法不是除法，而是采用每个素数，将其所有倍数标记为将其自身作为最低素数因子，除非已经标记。

int lpf[MAX] = {};
int primes[MAX_PRIME];

for(int i = 0; i < MAX_PRIME; ++i)
{
    int mult = primes[i];
    while(mult < MAX)
    {
       if (lpf[mult] == 0)
       {
            lpf[mult] = primes[i];
       }
       mult += primes[i];
    }
}

末尾未标记的数字本身就是质数，因此这种方法与查找 MAX 下的所有质数所花费的时间相同。

Answer 2

根据@Keith 的回答改编，新代码运行速度更快（旧速度的 13%！）：

    public void SieveDivisors() {
        int iNum, iPrime, i6Prime; 
        _iaFirstDivisors = new int[_iLimit];
        _iaFirstDivisors[1] = 1;
        //Start at the largest primes, then work down. This way, we never need to check if the
        // lowest prime multiple is already found, we just overwrite it
        //Also, skip any multiples of 2 or 3, because setting those is a waste of time
        for (int iPrimeIndex = _iaPrimes.Length - 1; iPrimeIndex >= 1; iPrimeIndex--) {
            iPrime = _iaPrimes[iPrimeIndex];
            i6Prime = iPrime * 6;
            for (iNum = iPrime; iNum < _iLimit; iNum += i6Prime) {
                _iaFirstDivisors[iNum] = iPrime;
            }
            for (iNum = iPrime * 5; iNum < _iLimit; iNum += i6Prime) {
                _iaFirstDivisors[iNum] = iPrime;
            }
        }
        //Then record all multiples of 2 or 3
        for (iNum = 3; iNum < _iLimit; iNum += 6) {
            _iaFirstDivisors[iNum] = 3;
        }
        for (iNum = 2; iNum < _iLimit; iNum += 2) {
            _iaFirstDivisors[iNum] = 2;
        }
    }

Answer 3

您说您正在使用阿特金筛法生成素数列表。如果您使用埃拉托色尼筛法，您会自动获得 LPD 阵列 - 它只是您用于筛分的阵列。而不是存储布尔轨道第一个使数字复合的素数。

这是一些伪 C 代码：

int lpd[MAX] = {};
int primes[MAX_PRIMES];
int nprimes = 0;

void sieve() {
  for (int p = 2; p*p < MAX; ++p) {
    if (lpd[p] == 0) {
      primes[nprimes++] = p;
      lpd[p] = p;
      for (int q = p*p; q < MAX; q += p) {
        if (lpd[q] == 0) { lpd[q] = p; }
      }
    }
  }
}

最后，数组 lpd[] 将包含最低素数，primes[] 将包含素数列表。

（相对）快速找到小于 10 000 000 的数的除数

(Relatively) Quickly find some divisor for a number < 10 000 000

c#

math

primes