C-программа для поиска простых коэффициентов, компиляция не останавливается

Question

Моя программа для вычисления наибольшего основного коэффициента 600851475143 застревает и никогда не останавливается во время компиляции и выполнения. Кто-нибудь знает, почему он не завершил выполнение?

#include <stdio.h> //Edited the #includes(typo) to #include 
int main (void) 
{ 

    long long int num = 600851475143 ; 
    long long int factorCount; 
    long long int bigFactor; 

    for (long long int i=1 ; i <= num; i+=2)// Iterating through all numbers from 2, smaller than or equal to num 
    { 
     if (num % i == 0) // If the number "i" is a factor of num i.e. If "i" perfectly divides num 
     { 
      factorCount = 0; 
      //checking whether a factor "i" , is a prime factor of num 
      for (long long int j=2; j <= i ; j++ ) // Iterating through all numbers from 2, smaller than or equal to "i" 
      { 
       if (i % j == 0) // If the number "j" prefectly divides or is a factor of "i" 
       { 
        factorCount++; //Add 1 to factorCount 
       }; 
      }; 

      if (factorCount == 1) // If factorCount has not exceeded 1 i.e., the number "i" is a prime number 
      { 
       bigFactor = i; 
      }; 
     }; 

    }; 
    printf("The largets prime factor of %lli is %lli\n",num,bigFactor); 

    return 0; 
} 

Answer 1

Я не уверен, понял ли я ваш вопрос .. так что вы просто хотите получить самый большой основной коэффициент для определенного числа? Если это так, то просто сделайте следующее:

#include <stdio.h> 

#define NUMBER 600851475143 

int main (void) 
{ 
    long long int num = NUMBER; 
    long long int factor; 

    for (factor=2 ; num != 1; factor++) { 
     if (num % factor == 0) { 
      num = num/factor; 
      factor = factor-1; 
     } 
    } 
    printf("The largets prime factor of %lli is %lli\n",NUMBER, factor); 
    return 0; 
} 

Почему это работает: первый главный фактор, вы найдете самый маленький первичный фактор числа; последний основной фактор является самым большим. Поэтому, как только вы нашли простой множитель p, не существует простого множителя, меньшего p, потому что в противном случае вы бы обнаружили, что меньший простой коэффициент раньше. Следовательно, ваш следующий простой коэффициент больше равен p.

Answer 2

Он заканчивает свое исполнение, это просто занимает много времени. Вы выполняете цикл 600851475143/2 раза или около 300 миллиардов раз. Если основной цикл занимает 1 мс для выполнения (но он должен занять больше, так как существует еще один внутренний цикл), то это означает, что требуемое время составит около 9,5 лет.

Просто будьте терпеливы, и ваша петля закончится.

Answer 3

Попробуйте это:

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
int main (void) 
{ 

    long long int num = 600851475143 ; 
    long long int factorCount; 
    long long int bigFactor; 
    for (long long int i=1 ; i <= sqrt(num); i+=2)// Iterating through all numbers from 2, smaller than or equal to num 
    { 
     if (num % i == 0) // If the number "i" is a factor of num i.e. If "i" perfectly divides num 
     { 
      factorCount = 0; 
      //checking whether a factor "i" , is a prime factor of num 
      for (long long int j=2; j <= i ; j++ ) // Iterating through all numbers from 2, smaller than or equal to "i" 
      { 
       if (i % j == 0) // If the number "j" prefectly divides or is a factor of "i" 
       { 
        factorCount++; //Add 1 to factorCount 
       }; 
      }; 

      if (factorCount == 1) // If factorCount has not exceeded 1 i.e., the number "i" is a prime number 
      { 
       bigFactor = i; 
      }; 
     }; 

    }; 
    printf("The largets prime factor of %lli is %lli\n",num,bigFactor); 

    return 0; 
} 

только calcule корень 600851475143.

Answer 4

Ну, моя догадка будет то, что он работает прекрасно, но занимает слишком много времени. Итак, вам нужно оптимизировать свой алгоритм. Вот некоторые подсказки для улучшения вашего алгоритма:

• Вам просто нужно, чтобы перебирать до квадратного корня из числа, чтобы узнать, является ли это простым.
• Как и в нашем внешнем цикле (но не во внутреннем цикле), вам просто нужно перебирать нечетные числа.
• Поскольку вы ищете самый высокий основной коэффициент, попробуйте начать с конца, и как только вы достигнете основного фактора, прекратите искать.

Я думаю, что это должно выполняться в разумные сроки.

EDIT: На самом деле, после отражения третья точка не так очевидна. Конечно, это лучше, чем идти через все факторы, но вычисление пути медленнее для больших факторов ...

Answer 5

Добрый день 24,

Среда выполнения этого кода будет принимать очень долго, очень долго. Но она должна работать, только реальная ошибка является «s» в

#includes <stdio.h> 

так просто быть терпеливым, вы имеете дело с очень большими числами, перебирая нечетные числа сделали гораздо менее длительным, чем это могло быть, don

Примечание: Если вы используете онлайн-среду IDE, такую ​​как cpp.sh или другой источник, веб-сайт, скорее всего, отключится. Используйте локально установленную среду IDE.

Answer 6

Это достаточно эффективно:

#include <stdio.h> 

#define NUMBER 600851475143 

static unsigned long long int gpf(unsigned long long n) 
{ 
    unsigned long long d, q; 

    while (n > 2 && !(n & 1)) 
     n >>= 1; 

    d = 3; 
    while (d * d <= n) { 
     q = n/d; 
     if (q * d == n) 
      n = q; 
     else 
      d += 2; 
    } 

    return n; 
} 

int main(void) 
{ 
    printf("The largest prime factor of %llu is %llu\n", 
      NUMBER, gpf(NUMBER)); 
    return 0; 
}