用于寻找主要因素的 C 程序，编译不会停止

Question

我的计算最大质因数 600851475143 的程序在编译和执行过程中卡住了，一直没有停止。有谁知道为什么它没有完成执行？

#include <stdio.h> //Edited the #includes(typo) to #include 
 int main (void)
{

    long long int num = 600851475143 ;
    long long int factorCount;
    long long int bigFactor;

    for ( long long int i=1 ; i <= num; i+=2 )// Iterating through all numbers from 2, smaller than or equal to num
    {
        if ( num % i == 0) // If the number "i" is a factor of num i.e. If "i" perfectly divides num
        {
            factorCount = 0;
            //checking whether a factor "i" , is a prime factor of num
            for ( long long int j=2; j <= i ; j++  ) // Iterating through all numbers from 2, smaller than or equal to "i"
            {
                if ( i % j == 0) // If the number "j" prefectly divides or is a factor of "i"
                {
                    factorCount++; //Add 1 to factorCount
                };
            };

            if ( factorCount == 1 ) // If factorCount has not exceeded 1 i.e., the number "i" is a prime number
            {
                bigFactor = i;
            };
        };

    };
    printf("The largets prime factor of %lli is %lli\n",num,bigFactor );

    return 0;
}

Answer 1

它完成了它的执行，只是需要很多时间。您正在执行循环 600851475143 / 2 次或大约 3000 亿次。如果主循环需要 1ms 来执行（但它应该需要更多，因为还有另一个内部循环）那么这意味着所需的时间大约是 9.5 年。

请耐心等待，您的循环将会结束。

Answer 2

试试这个：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 int main (void)
{

    long long int num = 600851475143 ;
    long long int factorCount;
    long long int bigFactor;
    for ( long long int i=1 ; i <= sqrt(num); i+=2 )// Iterating through all numbers from 2, smaller than or equal to num
    {
        if ( num % i == 0) // If the number "i" is a factor of num i.e. If "i" perfectly divides num
        {
            factorCount = 0;
            //checking whether a factor "i" , is a prime factor of num
            for ( long long int j=2; j <= i ; j++  ) // Iterating through all numbers from 2, smaller than or equal to "i"
            {
                if ( i % j == 0) // If the number "j" prefectly divides or is a factor of "i"
                {
                    factorCount++; //Add 1 to factorCount
                };
            };

            if ( factorCount == 1 ) // If factorCount has not exceeded 1 i.e., the number "i" is a prime number
            {
                bigFactor = i;
            };
        };

    };
    printf("The largets prime factor of %lli is %lli\n",num,bigFactor );

    return 0;
}

只计算600851475143的根

Answer 3

嗯，我最好的猜测是它运行非常好，但需要太多时间。所以你要做的就是优化你的算法。以下是改进算法的一些提示：

你只需要迭代直到一个数的平方根就可以知道它是否是素数。
正如您在我们的外循环中所做的那样（但不是在您的内循环中），您只需要遍历奇数。
由于您正在寻找最高的质因数，请尝试从末尾开始，一旦找到质因数，就停止寻找。

我认为这应该运行在合理的时间内完成。

编辑：实际上，经过反思，第三点并不是那么明显。当然，这比遍历所有因素要好，但是对于大因素，计算速度要慢得多...

Answer 4

24 号下午好，

这段代码的运行时间会非常长，非常长。但它应该有效，唯一真正的错误是

中的 's'

#includes <stdio.h>

所以请耐心等待，您正在处理非常大的数字，遍历奇数使得它比它应该的要短得多，don

注意：如果您使用在线 IDE（例如 cpp.sh 或其他来源），网站很可能会超时。请使用本地安装的 IDE.

Answer 5

我不确定我是否理解你的问题..所以你只是想获得某个数字的最大质因数？如果是这种情况，那么只需执行以下操作：

#include <stdio.h>

#define NUMBER 600851475143

int main (void)
{
    long long int num = NUMBER;
    long long int factor;

    for (factor=2 ; num != 1; factor++) {
        if (num % factor == 0) {
            num = num / factor;
            factor = factor-1;
        }
    }
    printf("The largets prime factor of %lli is %lli\n",NUMBER, factor);
    return 0;
}

为什么会这样：您找到的第一个质因数是该数的最小质因数；最后一个素数是最大的。因此，一旦你找到了一个质因数 p，就不存在比 p 小的质因数，否则你之前就会找到那个更小的质因数。因此，您的下一个质因数大于等于 p。

Answer 6

这是相当有效的：

#include <stdio.h>

#define NUMBER 600851475143

static unsigned long long int gpf(unsigned long long n)
{
    unsigned long long d, q;

    while (n > 2 && !(n & 1))
        n >>= 1;

    d = 3;
    while (d * d <= n) {
        q = n / d;
        if (q * d == n)
            n = q;
        else
            d += 2;
    }

    return n;
}

int main(void)
{
    printf("The largest prime factor of %llu is %llu\n",
           NUMBER, gpf(NUMBER));
    return 0;
}

用于寻找主要因素的 C 程序，编译不会停止

C-program for finding prime factors, compilation is not stopping

c

prime-factoring