确定最大质因数的函数

Question

我正在尝试用 JS 编写一个函数，该函数 return 是一个数字的最大 "prime" 因子。比如我运行maxPrimeFactor(57)，我应该return一个19。但是，我的功能只在部分时间有效。我编写了一个名为 isPrime 的辅助函数，它 return 是一个布尔值，指示给定数字是否为质数。

任何人都可以抽查我的逻辑并给我指示我可能要去的地方wrong/how我可以改进我的算法和实现吗？感谢任何帮助。

function isPrime(n){
    var flag = true;

    for (var i = 2; i < n / 2; i++) {
        if (n % i == 0) {
            flag = false;
            return flag;
        }
    }

    return flag;
}

function maxPrimeFactor (n) {
    var max = 1;

    for (var i = 1; i <= n/2; i++) {
        if (n % i == 0 && isPrime(i)) {
            max = i;
        }
    }

    return max; 
}

Answer 1

下面我给你一个用C++写的代码：

#include <cstdio>
#include <cmath>

int max(int x, int y)
{
    return x > y ? x : y;
}

int maxPrime(int x)
{
    int mx = -1;
    int curX = x;
    /*i * i <= x is correct, because there is only one prime factor larger than 
      Sqrt(x), it's power must be 1, and actually it is curX after this loop, because
      all prime factor less or equal than Sqrt(x) is eliminated.*/
    for(int i = 2; i * i <= x; ++i)
    {
        while(curX % i == 0)
        {
            /*Here i must be a prime. consider Prime factorization 
              x = p1^q1 * p2^q2 * p3^q3...(p1<p2<p3...)
              the first number that satisfied x % i == 0 must be p1, it's prime!
              and p2 > p1 so I can continue to enumerate i, don't need to reset i to 2.
              curX = x/(p1^q1 * p2^q2 * ... * pj^qj) and i = p[j+1]
             */
            curX /= i, mx = max(i, mx);
        }
    }
    return max(mx, curX);
}

int main()
{
    int n;
    scanf("%d", &n);
    //I suppose n is positive
    if(n == 1) //1 is not prime
        printf("No solution\n");
    else
        printf("%d\n", maxPrime(n));
    return 0;
}

此代码达到最坏情况运行时间 O(Sqrt(n))

而且你的代码是错误的，因为当n是质数时，你的代码无法得到正确的答案。

而且你的代码效率不高

如果你想要更快的代码，你可以学习 Pollard Rho 或 SQUFOF。

Answer 2

1 不是素数，因此如果您将 1 传递给函数，它将 return 1 作为最大素数因子，这是不正确的。也许检查 return 像 NaN 或 undefined 这样的值可能有助于防止无效值，这取决于您是否需要限制输入的范围。

    if (n < 2) {
        return NaN;
    }

你还需要考虑n是素数的情况。一种更有效的解决方法是将 max 初始化为 n，然后如果 max 不再设置，则最大素数为 n。

function maxPrimeFactor (n) {
    var max = n;
    for (var i = 2; i <= n/2; i++) {
        if (n % i == 0 && isPrime(i)) {
            max = i;
        }
    }
    return max;
}

由于算法只关心最大的质因数，如果从n/2开始倒数，可以进一步优化函数到return找到的第一个质因数，否则return个数。

由于 isPrime() 中的本地 var 标志不会使代码更具可读性或功能性，因此我将其删除。（此外，无需循环到 n/2，因为没有任何数字的素数大于它的平方根）；

function isPrime(n){
    for (var i = 2; i < Math.sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

确定最大质因数的函数

Function to determine largest prime factor

javascript

algorithm

numbers