c - 寻找最大的 gcd while 循环问题

Question

我在 Project Euler 中做问题 3 以找到最大的 gcd。我应该找到 600851475143m 的 gcd，但在我这样做之前我想找到一个较小的数字。这是问题的链接，我正在用 C 语言编写。

http://projecteuler.net/problem=3

我的 while 循环有问题。我的算法是有一个增加的数字（i）当且仅当余数为零时才继续划分给定的数字。给定的数字随着它被划分而减少。如果 i 和 the 等于给定数，则 i 是最大的 GCD。

这是我的代码：

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

int main()
{
int origNumber = 13195;
int i = 2;
while(origNumber / i != 1 && origNumber % i != 0)   
{

    if(origNumber % i == 0)
    {
        origNumber = origNumber / i;

    }
    if(origNumber == i)
        break;



    i++;

    printf("origNumber = %d i = %d\n", origNumber, i);
}




}

Answer 1

#include <stdio.h>

int main(void){
    int origNumber = 13195;
    int i = 2;
    while(i*i<origNumber){
        int isFactor = 0;
        while(origNumber % i == 0)
            isFactor = origNumber = origNumber / i;

        if(isFactor)
            printf("i = %d\n", i);
        i++;
    }
    printf("origNumber = %d\n", origNumber);
    return 0;
}

Answer 2

while 循环提前退出是因为

while (origNumber / i != 1  && origNumber % i != 0)
                            ^^^^^^^^^^^^^^^^^^^^^^

origNumber % i != 0 当 origNumber 不能被 i 整除时将变为假（这可能会在找到所有除数之前发生。

将循环语句更改为-：

while ((origNumber / i) != 1)