Questo generatore principale è inefficiente C ++?
-
04-07-2019 - |
Domanda
È 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
Soluzione
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.
Altri suggerimenti
Stai cercando un lotto più numeri di quelli che devi - al massimo devi solo andare su <= (sqrt(num))
.
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à .
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)
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).
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.