Est-ce que ce générateur primaire est inefficace C++?

Question

Est-ce considéré comme un générateur de nombre premier efficace. Il me semble que c'est assez efficace. Est-ce l'utilisation du flux qui rend le programme plus lent?

Je suis en train de le soumettre à SPOJ et il me dit que ma limite de temps 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 chiffres spécifiés dans l'entrée. (Voir ici pour plus de détails: Prime Generator Problem)

-Tomek

Answer 1

C'est un pas (sauter les nombres pairs) au-dessus de l'algorithme naïf. Je suggère le Sieve Of Eratosthenes comme un algorithme plus efficace. À partir du lien ci-dessus:

La complexité de l'algorithme est O ((nlogn) (loglogn)) avec une exigence mémoire de O (n). La version segmentée du tamis de Eratosthenes, 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 Evens n'est pas très bonne parce que vous trouverez un nombre pair ne pas être premier sur le premier test. Le tamis a une mémoire beaucoup plus grande, mais la complexité d'exécution est de loin supérieure pour les grands N.

Answer 2

Vous cherchez un lot plus de numéros que vous avez - tout au plus il vous suffit d'aller à <= (sqrt(num)).

Answer 3

Il peut être rendu légèrement plus efficace. Vous n'avez pas besoin de démarrer k à 2, vous vous assurez déjà de ne pas tester les nombres pairs. Donc, commencez k à 3.
Ensuite, incrémenter k par 2 à chaque fois parce que vous n'avez pas besoin de tester d'autres nombres pairs. Le moyen le plus efficace que je peux penser est de tester seulement si un nombre est divisible par des nombres premiers connus (alors quand vous en trouvez un autre, ajoutez-le à la liste avec laquelle vous testez).

Answer 4

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 RACINE (j), mais il est généralement assez bonne estimation.

Answer 5

Voici un simple tamis d'ératosthènes. Il ne nécessite pas de prédéclarer un grand tableau booléen, mais c'est toujours >> O (n) dans le temps et l'espace. Cependant, tant que vous avez assez de mémoire, il devrait être nettement plus rapide que votre méthode naï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 encore trop lent pour vous, vous pouvez poursuivre le Sieve of Atkin, une optimisation de Eratosthène Sieve. En réalité, ceux-ci ne sont relativement efficaces que si la gamme de nombres premiers à générer commence à être faible.Si la limite inférieure est déjà assez grande et la limite supérieure n'est pas beaucoup plus grande que la limite inférieure, alors les méthodes de tamisage sont un travail inutile et vous feriez mieux d'exécuter un primality test.

Answer 6

Et une chose, ne pas utiliser sqrt (n) dans une boucle:

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

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

Utilisez

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

Ou tout simplement

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