Ist das Prime-Generator ineffizient C ++?

Question

wird dies als ein effizienter Primzahl Generator gesehen. Es scheint mir, dass dies ziemlich effizient ist. Ist es die Verwendung des Stroms, der das Programm macht langsamer laufen?

Ich versuche, dies zu unterbreiten SPOJ und es sagt mir, dass meine Zeit überschritten ...

#include <iostream>
#include <sstream>

using namespace std;

int main() {
    int testCases, first, second, counter = 0;
    bool isPrime = true;
    stringstream out;

    cin >> testCases;

    for (int i = 0; i < testCases; i++) {
        // get the next two numbers
        cin >> first >> second;

        if (first%2 == 0)
            first++;

        // find the prime numbers between the two given numbers
        for (int j = first; j <= second; j+=2) {
            // go through and check if j is prime
            for (int k = 2; k < j; k++) {
                if (j%k == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                out << j << "\n";
            }
            isPrime = true;
        }
        out << "\n";
    }

    cout << out.str();

    return 0;
}

EDIT: Das Programm soll Primzahlen zwischen den Zahlen in der Eingabe angegeben erzeugen. (Siehe hier für weitere Informationen: Prime Generator Problem )

-Tomek

Answer 1

Dies ist ein Schritt über dem naiven Algorithmus (gerade Zahlen Überspringen). Ich würde vorschlagen, das Sieb des Eratosthenes als effizienter Algorithmus. Aus dem obigen Link:

  

Die Komplexität des Algorithmus ist   O ((n log n) (loglogn)) mit einem Speicher   Anforderung von O (n). die segmentierte   Version des Sieb des Eratosthenes,   mit basischen Optimierungen wie Rad   Faktorisierung, nutzt O (n) -Operationen   und O (n1 / 2loglogn / logn) Bits   Speicher.

Der Algorithmus Sie geben, ist irgendwo in der Nähe von O (n ^ 2). Der Speedup Sie erhalten durch Evens Skipping ist nicht so groß, weil Sie eine gerade Zahl nicht als Prime auf dem ersten Test finden würde. Das Sieb hat einen viel größeren Speicherbedarf, aber die Laufzeitkomplexität weit überlegen ist für großen N .

Answer 2

Du bist ein Los mehr Zahlen als Sie müssen -. Höchstens nur zu <= (sqrt(num)) gehen müssen

Answer 3

Hier ist ein einfaches Sieb des Eratosthenes. Es erfordert keine großen boolean Array predeclaring, aber es ist immer noch >> O (n) in Zeit und Raum. Solange Sie genügend Speicher haben, aber es sollte deutlich schneller sein als das, was Ihre derzeitige naive Methode.

#include <iostream>
#include <map>

using namespace std;

template<typename T = int, typename M = map<T, T> >
class prime_iterator {
    public:
        prime_iterator() : current(2), skips() { skips[4] = 2; }
        T operator*() { return current; }
        prime_iterator &operator++() {
            typename M::iterator i;
            while ((i = skips.find(++current)) != skips.end()) {
                T skip = i->second, next = current + skip;
                skips.erase(i);
                for (typename M::iterator j = skips.find(next);
                        j != skips.end(); j = skips.find(next += skip)) {}
                skips[next] = skip;
            }
            skips[current * current] = current;
            return *this;
        }
    private:
        T current;
        M skips;
};

int main() {
    prime_iterator<int> primes;
    for (; *primes < 1000; ++primes)
        cout << *primes << endl;
    return 0;
}

Wenn dies für Sie immer noch zu langsam ist, können Sie die Sieb des Atkin verfolgen wollen eine optimierte Sieb des Eratosthenes.

Eigentlich sind diese nur relativ effizient, wenn der Bereich der Primzahlen beginnt zu erzeugen, gering. Wenn die untere Grenze schon ziemlich groß ist und die obere Grenze ist nicht viel größer als die untere, dann sind die Sieben Methoden verschwenderisch Arbeit, und Sie wären besser dran, läuft ein Primzahltest .

Answer 4

Und noch etwas, nicht sqrt (n) in einer Schleife verwenden:

for(int k=1;k<sqrt(n);++k)

Wenn es keine gute Optimierung ist, wird sqrt in jeder Iteration berechnet werden.

Mit

for (int k=1;k*k < n;++k)

Oder einfach

int sq = sqrt ( n );
for (int k=1;k<sq;++k)

Answer 5

Es kann etwas effizienter gemacht werden. Sie brauchen nicht k auf 2 zu starten, sind Sie schon dafür, dass nicht testen gerade Zahlen. So starten k bei 3
Dann k erhöht jedes Mal um 2, weil Sie nicht andere gerade Zahlen testen müssen. Der effizienteste Weg, die ich denken kann, ist nur testen, ob eine Anzahl von bekannten Primzahlen teilbar ist (dann, wenn Sie ein anderes, dass Sie mit Test zur Liste hinzufügen finden).

Answer 6

for (int k = 2; k < j; k++) {
     if (j%k == 0) {
         isPrime = false;
         break;
     }
}

sollte:

for(int k = 3; k <= j/2; k+=2 )
{
  if( j % k == 0 )
      break;
}

j / 2 sollte wirklich sqrt (j) werden, aber es ist in der Regel gut genug Schätzung.