Warum funktioniert mein Programm nicht mit großen Zahlen?

Question

Ich versuche ein Programm zu schreiben, das den größten Primfaktor von 600851475143 findet. Es funktioniert perfekt mit kleineren Zahlen (bis 10000), aber nicht weiter. Wie kann ich es ändern? Das Programm gibt keinen Fehler oder beendet sich selbst, sondern gibt einfach nichts aus.

#include <iostream> 
#include <vector> 
using namespace std; 

bool isPrime(unsigned long long int num); 


int main() { 
    unsigned long long int m = 600851475143; 
    std::vector<int> pfactors; 
    pfactors.reserve(100000000); 
    for (long long int i = 2; i <= m; i++) { 
     if (isPrime(i) == true) { 
      if (m % i == 0) { 
       pfactors.push_back(i); 
      } 
     } 
     } 
    for (vector<int>::iterator it = pfactors.begin(); it != pfactors.end(); it++) { 
     cout << *it << endl; 
    } 
    cin.get(); 
    return 0; 
    } 




bool isPrime(unsigned long long int num) 
{ 
    if (num < 2) 
     return false; 


    if (num > 2 && (num % 2) == 0) 
     return false; 


    for (unsigned long long int i = 2; i < num; i++) 
    { 

     if ((num % i) == 0) 
     { 

      return false; 
     } 
    } 


    return true; 
} 

Answer 1

600851475143 ist eine sehr große Anzahl und Ihr Algorithmus ist sehr ineffizient. Ich vermute, dass es irgendwann enden würde, aber das "irgendwann" ist weit mehr als die Zeit, die Sie warten würden.

Das obige geht davon aus, dass long long auf Ihrer Plattform sogar in der Lage ist, die Nummer zu repräsentieren - wenn es nur 32Bits ist, dann ist es nicht.

Was Sie wirklich brauchen, ist ein effizienter Algorithmus.

Answer 2

Ihr Programm schlägt fehl, weil Sie den Datentyp int verwenden. Es hat 32 bits, i.e 2^32 ~= 9 digits max

Um auf einige Werte zuzugreifen, die größer als 9 Ziffern sind, verwenden Sie long long oder unsigned long long. Es hat 64 bits, i.e 2^64 ~= 18 digits for signed and 20 digits for unsigned.

Edit:^Das ist für C++ 98 (Orwell Dev C++: Geprüft)

vector<int> pfactor; 

Dieser int auf Vektor macht Ihr Programm fehlschlagen. Und Sie müssen keinen Platz in einem Vektor reservieren, da er dynamisch ist, es sei denn, Sie arbeiten an 2D-Vektoren.

Beispielcode:

#include<math.h> 
#include<iostream> 
using namespace std; 

bool ifPrime (int number) { 
    for (long long int i=2; i<sqrt(number); ++i) { 
     if (number%i == 0) return false; 
    } 

    return true; 
} 

int main () { 
    long long int number = 600851475143; 
    static long long int largestPrime; 

    bool found = false; 
    for (long long int i=sqrt(number); i>=0 && !found; i=i-1) { 
     if (number%i==0 && ifPrime(i)) { 
      largestPrime = i; 
      found = true; 
     } 
    } 

    cout << "Largest Prime for " << number << " is: " << largestPrime << endl; 
} 

Answer 3

Antworten von @DanyalImran zur Verfügung gestellt und @ Jean-FrançoisFabre sind beide falsch. Es ist co-incidence, dass 600851475143 ein Produkt von 71, 839, 1471 und 6857 ist und alle Teiler weniger als sqrt (num) sind. Was wäre, wenn die Nummer im OP wäre 60085147514 (die Primzahl)?

Also müssen wir einen vollen Bereich suchen [2, num], nicht den Bereich [2, sqrt (num)].

Also, hier ist, was ich nach ein paar Versuchen, die Suche optimiert mit beiden Sieve von Eratosthenes Algorithmus, um einen Vektor von Prime Flags vorausberechnen und zuvor gefundenen Primzahlen zu speichern.

Obwohl das Sieve von Eratosthenes wirklich ein schneller Weg ist, alle Primzahlen in einem bestimmten Bereich zu finden (es gibt keine Division, nur Multiplikationen, die mal schneller sind als Divisionen), kann dieser Ansatz nicht viel helfen Eliminieren Sie die Notwendigkeit, den Vektor zu durchlaufen, um Elemente zu finden, die als Primzahlen markiert sind, und teilen Sie dann die betreffende Zahl durch die gefundene Primzahl (ich ersetzte vector<bool> durch in der @ Jean-FrançoisFabre-Implementierung absichtlich, um eine mögliche "bitgepackte" Implementierung zu vermeiden vector<bool> als eine Bitposition in einer Vektorberechnung ist definitiv teurer als eine char Positionsberechnung).

Die Zeit, die ich bekomme, um die Aufgabe in OP für 150212868857 Prime zu lösen ist ~ 7: 05 Minuten auf meiner 1.4 GHz AMD:

150212868857 

real 7m5.156s 
user 7m5.063s 
sys 0m0.008s 

Der Versuch, alle zuvor gefundenen Primzahlen merken Sie sich die isPrime() Test zur Beschleunigung ist noch schlimmer, so habe ich es nicht eine Chance geben zu beenden. Dies wird durch die gleiche Notwendigkeit erklärt, durch einen Vektor von Primzahlen zu iterieren, und es ist aufgrund der Menge der aus dem Speicher zu lesenden Daten noch teurer.

Die letzte Variante ist nur eine Iteration des Kandidaten Divisor im Bereich 3-num mit Schritt 2 und die isPrime nur anrufen, wenn num sogar Kandidaten ist. Dieser Ansatz zeigt die gleiche Zeit wie das vorherige Plus minus ein paar Sekunden. So scheint der Zugriff auf ein Vektorelement so teuer wie eine Division zu sein, sobald die verwendete Mathematik in native Register einer modernen CPU passt.

Wenn jedoch die fragliche Nummer nicht prim ist (wie im OP), gibt es immer noch einen Platz für die Optimierung, der es erlaubt, die Suchzeit zu verkürzen.

der Code:

#include <iostream> 
#include <vector> 
#include <math.h> 

using namespace std; 

//#define SIEVE 
vector<char> primeFlagger; 

void initSieve(unsigned long long int limit) { 
    unsigned long long int root = (unsigned long long int)(sqrt(limit)); 
    primeFlagger = vector<char>(root+1,true); 
    primeFlagger[0] = primeFlagger[1] = false; 

    for(unsigned long long int j=2; j<=root; j++) 
    { 
     if(primeFlagger[j]) 
     { 
      for(unsigned long long int k=j; (k*j)<=root; k++) 
      { 
       primeFlagger[j*k]=false; 
      } 
     } 
    } 
} 

#ifdef SIEVE 
bool isPrime(unsigned long long int num) 
{ 
    if (num <= 2) 
     return true; 

    if ((num % 2) == 0) 
     return false; 

    unsigned sqr = (unsigned)sqrt(num); 
    for(unsigned i = 3; i <= sqr; i+=2) { 
     if (primeFlagger[i] && num % i == 0) 
      return false; 
    } 

    return true; 
} 
#else 
bool isPrime(unsigned long long int num) 
{ 
    if (num <= 2) 
     return true; 

    if ((num % 2) == 0) 
     return false; 

    unsigned sqr = (unsigned)sqrt(num); 
    for(unsigned i = 3; i <= sqr; i+=2) { 
     if (num % i == 0) 
      return false; 
    } 

    return true; 
} 
#endif 

int main() { 
    unsigned long long int m = 600851475143;//150212868857;//600851475149; 
    std::vector<unsigned long long int> pfactors; 

#ifdef SIEVE 
    initSieve(m); 
#endif 

    if (m % 2 == 0) { 
     do { 
      m /= 2; 
     } while (m % 2 == 0); 
     pfactors.push_back(2); 
    } 

    for (long long int i = 3; i <= m; i+=2) { 
     if (m % i == 0 && isPrime(i)) { 
      do { 
       m /= i; 
      } while (m % i == 0); 
      pfactors.push_back(i); 
     } 
    } 

    for (vector<unsigned long long int>::iterator it = pfactors.begin(); it != pfactors.end(); it++) { 
     cout << *it << endl; 
    } 

    return 0; 
} 

das Ergebnis mit Nummer im OP:

$ g++ -O3 prime1.cpp 
$ time ./a.out 
71 
839 
1471 
6857 

real 0m0.004s 
user 0m0.002s 
sys 0m0.002s