c - 最大の gcd while ループの問題を見つける

Question

最大の gcd を見つけるために、Project Euler で問題 3 を実行しています。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

while ループは次の理由で早期に終了しています。

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

origNumber % i != 0 origNumber が i で割り切れない場合は false になります (これは、すべての約数が見つかる前に発生する可能性があります。

ループ ステートメントを次のように変更します。

while ((origNumber / i) != 1)