Mon tamis de Eratosthenes prend trop de temps

Question

J'ai mis en œuvre Sieve of Eratosthenes pour résoudre le problème SPOJPRIME1. Bien que la sortie soit bonne, ma soumission dépasse la limite de temps. Comment puis-je réduire le temps d'exécution?

int main() 
{ 
    vector<int> prime_list; 
    prime_list.push_back(2); 
    vector<int>::iterator c; 
    bool flag=true; 
    unsigned int m,n; 
    for(int i=3; i<=32000;i+=2) 
    { 
    flag=true; 
    float s = sqrt(static_cast<float>(i)); 
    for(c=prime_list.begin();c<=prime_list.end();c++) 
    { 
     if(*c>s) 
      break; 
     if(i%(*c)==0) 
     { 
      flag=false; 
      break; 
     } 
    } 
    if(flag==true) 
    { 
     prime_list.push_back(i); 
    } 
    } 
    int t; 
    cin>>t; 
    for (int times = 0; times < t; times++) 
    { 
    cin>> m >> n; 
    if (t) cout << endl; 
    if (m < 2) 
     m=2; 
    unsigned int j; 
    vector<unsigned int> req_list; 
    for(j=m;j<=n;j++) 
    { 
     req_list.push_back(j); 
    } 
    vector<unsigned int>::iterator k; 
    flag=true; 
    int p=0; 
    for(j=m;j<=n;j++) 
    { 
     flag=true; 
     float s = sqrt(static_cast<float>(j)); 
     for(c=prime_list.begin();c<=prime_list.end();c++) 
     { 
      if((*c)!=j) 
      { 
       if((*c)>s) 
        break; 
       if(j%(*c)==0) 
       { 
        flag=false; 
        break; 
       } 
      } 
     } 
     if(flag==false) 
     { 
      req_list.erase (req_list.begin()+p); 
      p--; 
     } 
     p++; 
    } 
    for(k=req_list.begin();k<req_list.end();k++) 
    { 
     cout<<*k; 
     cout<<endl; 
    } 
    } 
} 

Answer 1

Affichez votre code, trouvez les points chauds et éliminez-les. Windows, Linux liens profileurs.

Answer 2

Je pense qu'une façon d'accélérer légèrement votre tamis est la prévention de l'utilisation de l'opérateur mod dans cette ligne.

if(i%(*c)==0)

au lieu de l'opération mod coûteux (relativement), peut-être si vous Iterated avant dans votre tamis avec addition.

Honnêtement, je ne sais pas si c'est correct. Votre code est difficile à lire sans commentaires et avec des noms de variable à lettre unique.

Answer 3

Je jetterais ce que vous avez et recommencerais avec un simple la mise en œuvre d'un tamis, et seulement ajouter plus de complexité si vraiment nécessaire. Voici un point de départ possible:

#include <vector> 
#include <iostream> 

int main() { 
    int number = 32000; 
    std::vector<bool> sieve(number,false); 
    sieve[0] = true; // Not used for now, 
    sieve[1] = true; // but you'll probably need these later. 

    for(int i = 2; i<number; i++) { 
     if(!sieve[i]) { 
      std::cout << "\t" << i; 
      for (int temp = 2*i; temp<number; temp += i) 
       sieve[temp] = true; 
     } 
    } 
    return 0; 
} 

Pour la plage donnée (jusqu'à 32000), cela va en moins d'une seconde (avec sortie dirigée vers un fichier - à l'écran, il va généralement plus lent). C'est à vous de voir à partir de là ...

Answer 4

Votre code est lent car vous n'avez pas implémenté l'algorithme Sieve of Eratosthenes. L'algorithme fonctionne de cette façon:

1) Create an array with size n-1, representing the numbers 2 to n, filling it with boolean values true (true means that the number is prime; do not forget we start counting from number 2 i.e. array[0] is the number 2) 
2) Initialize array[0] = false. 
3) Current_number = 2; 
3) Iterate through the array by increasing the index by Current_number. 
4) Search for the first number (except index 0) with true value. 
5) Current_number = index + 2; 
6) Continue steps 3-5 until search is finished. 

Cet algorithme prend l'heure O (nloglogn). Ce que vous faites prend beaucoup plus de temps (O (n^2)). Btw dans la deuxième étape (où vous recherchez des nombres premiers entre n et m) vous n'avez pas à vérifier si ces nombres sont à nouveau premiers, idéalement vous les aurez calculés dans la première phase de l'algorithme. Comme je vois dans le site que vous avez lié le problème principal est que vous ne pouvez pas réellement créer un tableau avec la taille n-1, parce que le nombre maximum n est 10^9, causant des problèmes de mémoire si vous le faites avec cette manière naïve. Ce problème est à vous :)

Answer 5

Je ne suis pas vraiment sûr que vous ayez implémenté le tamis des Erasthotènes. Quoi qu'il en soit, un certain nombre de choses pourraient accélérer dans une certaine mesure votre algorithme: Éviter plusieurs rellocations du contenu vectoriel en préallouant de l'espace (recherche std::vector<>::reserve). L'opération sqrt est cher, et vous pouvez probablement l'éviter complètement en modifiant les essais (arrêt lorsque le x*x > y au lieu de vérifier x < sqrt(y).

Là encore, vous obtiendrez une amélioration beaucoup mieux en révisant l'algorithme réel. D'un sommaire regardez comme si vous itérez sur tous les candidats et pour chacun d'entre eux, en essayant de diviser avec tous les nombres premiers connus qui pourraient être des facteurs.Le tamis d'Erasthotenes prend un seul premier et rejette tous les multiples de ce premier en un seul passage

Notez que le tamis n'effectue aucune opération pour tester si un nombre est premier, s'il n'a pas été mis au rebut avant que ce soit un nombre premier. ou chaque facteur unique.D'autre part, votre algorithme traite plusieurs fois plusieurs nombres (contre les nombres premiers existants)

Answer 6

La façon dont je comprends le problème est que vous devez générer tous les nombres premiers dans une plage [m, n]. Une manière de faire cela sans avoir à calculer tous les nombres premiers à partir de [0, n], parce que c'est probablement ce qui vous ralentit, est de générer d'abord tous les nombres premiers dans la plage [0, sqrt (n)] . Ensuite, utilisez le résultat pour tamiser dans la plage [m, n]. Pour générer la liste initiale des nombres premiers, implémentez une version basique du crible d'Eratosthène (à peu près, une implémentation naïve du pseudo code de l'article Wikipédia fera l'affaire).

Cela devrait vous permettre de résoudre le problème en très peu de temps.

Voici une mise en œuvre simple échantillon du tamis d'Eratosthène:

std::vector<unsigned> sieve(unsigned n) { 
    std::vector<bool> v(limit, true); //Will be used for testing numbers 
    std::vector<unsigned> p;   //Will hold the prime numbers 

    for(unsigned i = 2; i < n; ++i) { 
     if(v[i]) {     //Found a prime number 
      p.push_back(i);    //Stuff it into our list 

      for(unsigned j = i + i; j < n; j += i) { 
       v[i] = false;   //Isn't a prime/Is composite 
      } 
     } 
    } 

    return p; 
} 

Il retourne un vecteur ne contenant que les nombres premiers de 0 à n. Ensuite, vous pouvez l'utiliser pour implémenter la méthode que j'ai mentionnée. Maintenant, je ne fournirai pas l'implémentation pour vous, mais vous devez faire la même chose que dans le crible d'Eratosthène, mais au lieu d'utiliser tous les entiers [2, n], vous utilisez simplement le résultat que vous avez trouvé. Vous ne savez pas si c'est trop donner?

Answer 7

Depuis l'origine dans la question SPOJ problem ne précise pas qu'il doit être résolu avec le Crible d'Eratosthène, voici une solution alternative basée sur this article. Sur mon ordinateur portable de six ans, il fonctionne en environ 15 ms pour le pire cas de test unique (n-m = 100 000).

#include <set> 
#include <iostream> 

using namespace std; 

int gcd(int a, int b) { 
    while (true) { 
     a = a % b; 

     if(a == 0) 
     return b; 

     b = b % a; 

     if(b == 0) 
     return a; 
    } 
} 

/** 
* Here is Rowland's formula. We define a(1) = 7, and for n >= 2 we set 
* 
* a(n) = a(n-1) + gcd(n,a(n-1)). 
* 
* Here "gcd" means the greatest common divisor. So, for example, we find 
* a(2) = a(1) + gcd(2,7) = 8. The prime generator is then a(n) - a(n-1), 
* the so-called first differences of the original sequence. 
*/ 
void find_primes(int start, int end, set<int>* primes) { 
    int an;  // a(n) 
    int anm1 = 7; // a(n-1) 
    int diff; 

    for (int n = start; n < end; n++) { 
     an = anm1 + gcd(n, anm1); 

     diff = an - anm1; 

     if (diff > 1) 
     primes->insert(diff); 

     anm1 = an; 
    } 
} 

int main() { 
    const int end = 100000; 
    const int start = 2; 

    set<int> primes; 

    find_primes(start, end, &primes); 
    ticks = GetTickCount() - ticks; 

    cout << "Found " << primes.size() << " primes:" << endl; 

    set<int>::iterator iter = primes.begin(); 
    for (; iter != primes.end(); ++iter) 
     cout << *iter << endl; 
}