C-Programm zum Auffinden von Primfaktoren, Kompilierung stoppt nicht

Question

Mein Programm zur Berechnung des größten Primefaktors von 600851475143 bleibt hängen und hört während der Kompilierung und Ausführung nie auf. Weiß jemand, warum es die Ausführung nicht beendet?

#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

Ich bin mir nicht sicher, ob ich Ihre Frage verstanden habe. Sie wollen also nur den größten Primfaktor für eine bestimmte Nummer bekommen? Wenn dies der Fall ist, dann tun Sie einfach die folgenden Schritte aus:

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

Warum dies funktioniert: der erste Primfaktor Sie die kleinste Primfaktor der Zahl finden ist; der letzte Primfaktor ist der größte. Wenn Sie also einen Primfaktor p gefunden haben, gibt es keinen Primfaktor kleiner als p, weil Sie sonst diesen kleineren Primfaktor früher gefunden hätten. Daher ist Ihr nächster Primfaktor größer gleich p.

Answer 2

Es beendet seine Ausführung, es dauert nur eine Menge Zeit. Sie führen eine Schleife 600851475143/2 mal oder etwa 300 Milliarden mal. Wenn die Hauptschleife 1 ms benötigt, um ausgeführt zu werden (aber es sollte mehr dauern, da es eine weitere innere Schleife gibt), bedeutet dies, dass die benötigte Zeit ungefähr 9,5 Jahre betragen würde.

Seien Sie einfach geduldig und Ihre Schleife wird beendet.

Answer 3

Try this:

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

Nur Calcule der Wurzel 600851475143.

Answer 4

Nun, meine beste Vermutung wäre, dass es völlig in Ordnung, läuft aber zu viel Zeit in Anspruch nimmt. Also, was Sie tun müssen, ist Ihren Algorithmus zu optimieren. Hier sind einige Hinweise für die Verbesserung Ihres Algorithmus:

• Sie müssen nur bis zur Quadratwurzel einer Zahl wiederholen, ob oder nicht zu wissen, dass es eine Primzahl ist.
• Wie Sie in unserer äußeren Schleife (aber nicht in Ihrer inneren Schleife) getan haben, müssen Sie nur durch ungerade Zahlen iterieren.
• Da Sie nach dem höchsten Primfaktor suchen, versuchen Sie am Ende zu beginnen und sobald Sie einen Primfaktor erreicht haben, hören Sie auf zu suchen.

Ich denke, dass dies in einer angemessenen Zeit laufen sollte.

EDIT: Eigentlich ist nach der Reflexion der dritte Punkt nicht so offensichtlich. Natürlich ist es besser, als alle Faktoren durchlaufen, aber die Berechnung ist viel langsamer für große Faktoren ...

Answer 5

Good Afternoon 24,

Die Laufzeit dieses Codes sehr lange dauern wird, sehr, sehr lange. Aber es sollte funktionieren, nur wirkliche Fehler ist das ‚s‘ in

#includes <stdio.h> 

so einfach geduldig sein, sind Sie mit sehr großen Zahlen zu tun, Iterieren durch ungerade Zahlen gemacht hat es viel weniger langwierig als es sein könnte, don

Hinweis: Wenn Sie eine Online-IDE wie cpp.sh oder eine andere Quelle verwenden, wird die Website höchstwahrscheinlich eine Zeitüberschreitung haben. Bitte verwenden Sie eine lokal installierte IDE.

Answer 6

Dies ist einigermaßen effizient:

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