Ce premier générateur est-il inefficace en C ++?

Question

Est-ce considéré comme un générateur de nombres premiers efficace? Il me semble que c'est assez efficace. Est-ce l'utilisation du flux qui ralentit l'exécution du programme?

J'essaie de soumettre ceci à SPOJ et il m'indique que mon délai a été dépassé ...

#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: le programme est censé générer des nombres premiers entre les nombres spécifiés dans l’entrée. (Voir ici pour plus de détails: problème lié au générateur principal )

-Tomek

Answer 1

C’est une étape (en sautant les nombres pairs) au-dessus de l’algorithme naïf. Je suggérerais le Sieve Of Eratosthenes comme algorithme plus efficace. À partir du lien ci-dessus:

  

La complexité de l'algorithme est   O ((nlogn) (loglogn)) avec une mémoire   exigence de O (n). Le segmenté   version du tamis d'Eratosthène,   avec des optimisations de base telles que la roue   factorisation, utilise O (n) opérations   et O (n1 / 2loglogn / logn) bits de   mémoire.

L'algorithme que vous donnez est quelque part près de O (n ^ 2). L'accélération que vous obtenez en sautant des événements n'est pas terrible, car vous constateriez qu'un nombre pair n'est pas primordial lors du premier test. Le tamis nécessite beaucoup plus de mémoire, mais la complexité de l'exécution est bien supérieure pour les N .

.

Answer 2

Vous recherchez beaucoup plus de numéros que nécessaire - au plus il vous suffit d'aller à <= (sqrt(num)).

Answer 3

Voici un tamis simple d’Ératosthène. Il n'est pas nécessaire de déclarer préalablement un grand tableau booléen, mais cela reste & Gt; & Gt; O (n) dans le temps et dans l'espace. Si vous avez assez de mémoire, elle devrait être sensiblement plus rapide que votre méthode na & # 239; ve actuelle.

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

Si cela est toujours trop lent pour vous, vous pouvez poursuivre le Sieve of Atkin , un tamis d’eratosthènes optimisé.

En fait, ils ne sont relativement efficaces que si le nombre de nombres premiers à générer est faible. Si la limite inférieure est déjà assez grande et que la limite supérieure n'est pas beaucoup plus grande que la limite inférieure, les méthodes de tamisage sont un travail inutile et il vaudrait mieux utiliser un test de primalité .

Answer 4

Et encore une chose, n'utilisez pas sqrt (n) dans une boucle:

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

S'il n'y a pas de bonne optimisation, sqrt sera calculé à chaque itération.

Utiliser

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

Ou simplement

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

Answer 5

Cela peut être légèrement plus efficace. Vous n'avez pas besoin de commencer k à 2, vous vous assurez déjà de ne pas tester les nombres pairs. Alors commencez k à 3.
Puis incrémentez k de 2 à chaque fois car vous n'avez pas besoin de tester d'autres nombres pairs. Le moyen le plus efficace auquel je puisse penser est de ne tester que si un nombre est divisible par des nombres premiers connus (puis lorsque vous en trouvez un autre, ajoutez-le à la liste avec laquelle vous testez).

Answer 6

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

devrait être:

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

j / 2 devrait vraiment être sqrt (j) mais c’est généralement une estimation assez bonne.