C 错误找到最大的质因数

Question

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool isPrime(unsigned long long x) {
    if (x % 2 == 0)
        return false;
    for (unsigned long long i = 3; i < sqrt(x); x += 2) {
        if (x % i == 0)
            return false;
    }
    return true;
}

int main(int argc, char const *argv[]) {
    unsigned long long largest, number = 13195;

    for (unsigned long long i = 2; i < number; i++) {
        if (isPrime(i) && number % i == 0) {
            largest = i;
        }
    }

    printf("Largest : %llu\n", largest);

    return EXIT_SUCCESS;
}

素数函数是否有效？如果我删除 for 循环中的 sqrt()，我得到的最终结果为 0，这很奇怪......

我得到的输出为 7，但最大的质因数应该是 29 为什么会发生这种情况？

Answer 1

这里有一个错字：

x += 2

应该

i += 2

这使你的isPrime(29)回报false。

顺便说一句，为什么要打扰？一个更简单的解决方案是将数字分解：

unsigned long long number = 13195;
unsigned long long i, max = 2;
unsigned long long orig = number;

for (i = 2; i <= orig; i++) {
    while (number % i == 0) {
        number /= i;
        max = i;
    }
}

printf("largest: %llu\n", max);