Questo generatore principale è inefficiente C ++?

Question

È visto come un generatore di numeri primi efficiente. Mi sembra che sia abbastanza efficiente. È l'uso dello stream che rende il programma più lento?

Sto provando a inviarlo a SPOJ e mi dice che il mio limite di tempo ha superato ...

#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: il programma dovrebbe generare numeri primi tra i numeri specificati nell'input. (Vedi qui per maggiori dettagli: Problema del generatore principale )

-Tomek

Answer 1

Questo è un passo (saltare i numeri pari) sopra l'algoritmo ingenuo. Suggerirei Sieve Of Eratosthenes come algoritmo più efficiente. Dal link sopra:

  

La complessità dell'algoritmo è   O ((nlogn) (loglogn)) con una memoria   requisito di O (n). Il segmentato   versione del setaccio di Eratostene,   con ottimizzazioni di base come la ruota   fattorizzazione, utilizza le operazioni O (n)   e O (n1 / 2loglogn / logn) bit di   la memoria.

L'algoritmo che dai è da qualche parte vicino a O (n ^ 2). L'accelerazione che ottieni saltando i pari non è eccezionale perché troverai un numero pari che non sarà il numero primo nel primo test. Il setaccio ha un requisito di memoria molto maggiore, ma la complessità del runtime è di gran lunga superiore per N di grandi dimensioni.

Answer 2

Stai cercando un lotto più numeri di quelli che devi - al massimo devi solo andare su <= (sqrt(num)).

Answer 3

Ecco un semplice setaccio di Eratostene. Non richiede la dichiarazione di un grande array booleano, ma è ancora & Gt; & Gt; O (n) nel tempo e nello spazio. Fintanto che hai abbastanza memoria, tuttavia, dovrebbe essere notevolmente più veloce di quello che il tuo attuale metodo & # 239; ve.

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

Se questo è ancora troppo lento per te, potresti voler perseguire Sieve of Atkin , un setaccio ottimizzato di Eratostene.

In realtà, questi sono relativamente efficienti solo se l'intervallo di numeri primi da generare inizia in basso. Se il limite inferiore è già abbastanza grande e il limite superiore non è molto più grande di quello inferiore, i metodi di setacciatura sono un lavoro dispendioso e faresti meglio a eseguire un test di primalità .

Answer 4

E un'altra cosa, non usare sqrt (n) in un ciclo:

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

Se non c'è una buona ottimizzazione, sqrt verrà calcolato in ogni iterazione.

Usa

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

O semplicemente

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

Answer 5

Può essere reso leggermente più efficiente. Non hai bisogno di iniziare k da 2, ti stai già assicurando di non testare i numeri pari. Quindi inizia k da 3.
Quindi incrementare k di 2 ogni volta perché non è necessario testare altri numeri pari. Il modo più efficiente che mi viene in mente è testare solo se un numero è divisibile per numeri primi noti (quindi quando ne trovi un altro aggiungi quello alla lista con cui collaudi).

Answer 6

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

dovrebbe essere:

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

j / 2 dovrebbe davvero essere sqrt (j) ma è in genere una stima abbastanza buona.