найти самые большие проблемы с контуром gcd

Question

Я делаю проблему 3 в Project Euler в поиске самого большого gcd. Я должен найти gcd для 600851475143m, но я хочу найти его с меньшим числом, прежде чем я это сделаю. Вот ссылка на проблему, я пишу это в С.

http://projecteuler.net/problem=3

У меня возникли проблемы с моим циклом. Мой алгоритм состоит в том, чтобы иметь увеличивающееся число (i) продолжать делить данное число тогда и только тогда, когда остаток равен нулю. Данное число уменьшается по мере его деления. Если i и a равно заданному числу, то 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 (origNumber/i != 1 && origNumber % i != 0) 
          ^^^^^^^^^^^^^^^^^^^^^^ 

origNumber % i != 0 станет ложным, когда origNumber не делится на I (который, вероятно, произойдет, прежде чем все делители

Измените оператор цикла на:

while ((origNumber/i) != 1) 

Answer 2

#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; 
}