我的 C 代码没有输出任何东西，或者结束 运行

Question

我正在尝试回答这个问题：

13195的质因数是5、7、13、29

数 600851475143 的最大质因数是多少？

这是我的代码：

#include <stdio.h>

int isPrime(long long num)
{
    for (long long k = 1; k < num; k++)
    {
            if (num%k == 0)
                    return 0;
    }

    return 1;
} 
long long num = 600851475143;
int main(void)
{
    long long prime_factor = 0;
    for (long long j = 2; j < num; j++)
    {
            if (num % j == 0 && isPrime(j) == 1)
                    prime_factor = j;
    }

    printf("%lli\n", prime_factor);


}

但由于某种原因它不打印任何东西，甚至不结束。这是什么原因造成的？

Answer 1

它不打印任何东西，因为它从不离开循环，之后发现代码中唯一打印任何东西的行。尝试一个较小的数字，看看它是否结束。

Answer 2

这是一种非常低效的求数质因数的方法。

要找到质因数，您应该：

1. Create a static list of primes less than or equal to (number / 2).
2. Iterate over each element in the list of primes and see if each one can evenly divide the number.
3. Divide the original number by the prime, and check the last number again.

为什么？那么最小的素数是 2。如果数字不是偶数，那么可以整除任何大于 2 的数字的第一个素数是 3.

每个数字都可以通过其质因数来唯一标识。这叫做Fundamental Theorem of Arithmetic。这意味着只有一种方式来表示例如15 作为质数的乘积，在本例中为 { 3, 5 }。

然而任何素数都可以整除一个数不止一次。例如，49 是两个素数 { 7, 7 } 的乘积。将原始数字除以其因子之一可以使后续除法更快。当数字 == 1 时，您可以从逻辑上停止检查。