真是个奇怪的限制；2147483742 = 2 ^ 31 + 94.

What an odd limit; 2147483742 = 2^31 + 94.

正如其他人所指出的那样，对于一个数字，这个很小的按质数的除法很有可能足够快.只有这样，您才可以尝试Pollard的rho方法:

As others have pointed out, for a number this small trial division by primes is most likely fast enough. Only if it isn't, you could try Pollard's rho method:

/* WARNING! UNTESTED CODE! */
long rho(n, c) {
    long t = 2;
    long h = 2;
    long d = 1;

    while (d == 1) {
        t = (t*t + c) % n;
        h = (h*h + c) % n;
        h = (h*h + c) % n;
        d = gcd(t-h, n); }

    if (d == n)
        return rho(n, c+1);
    return d;
}

被称为 rho(n，1)，此函数返回 n 的(可能是复合的)因子；如果要查找 n 的所有因素，请将其循环并重复调用.您还需要一个素数检查器；对于您的极限，以2、7和61为基数的Rabin-Miller测试被证明是准确且相当快的.您可以在我的博客中阅读有关质数编程的更多信息.

Called as rho(n,1), this function returns a (possibly-composite) factor of n; put it in a loop and call it repeatedly if you want to find all the factors of n. You'll also need a primality checker; for your limit, a Rabin-Miller test with bases 2, 7 and 61 is proven accurate and reasonably fast. You can read more about programming with prime numbers at my blog.

但是在任何情况下，考虑到这么小的限制，我认为***使用素数除法.其他任何事物可能在渐近上更快，但实际上更慢.

But in any case, given such a small limit I think you are better off using trial division by primes. Anything else might be asymptotically faster but practically slower.

该答案最近收到了几次投票，因此我要添加一个简单的程序，该程序车轮分解，带有2,3,5-车轮.称为 wheel(n)，此程序按升序打印 n 的因子.

This answer has received several recent upvotes, so I'm adding a simple program that does wheel factorization with a 2,3,5-wheel. Called as wheel(n), this program prints the factors of n in increasing order.

long wheel(long n) {
    long ws[] = {1,2,2,4,2,4,2,4,6,2,6};
    long f = 2; int w = 0;

    while (f * f <= n) {
        if (n % f == 0) {
            printf("%ld\n", f);
            n /= f;
        } else {
            f += ws[w];
            w = (w == 10) ? 3 : (w+1);
        }
    }
    printf("%ld\n", n);

    return 0;
}

我在我的博客中讨论了车轮分解.解释很长，所以我在这里不再重复.对于适合 long 的整数，不太可能显着改善上面给出的 wheel 函数.

I discuss wheel factorization at my blog; the explanation is lengthy, so I won't repeat it here. For integers that fit in a long, it is unlikely that you will be able to significantly better the wheel function given above.