C++ Girl
  1. C++ Girl
  3. C ++ Numéro tâche du livre
Intereting Posts
Comment forcer la fenêtre Mac au premier plan? pourquoi tous les iterators / adaptateurs d’iterators non déplaçables en C ++ 11? Comment vérifier par programme la bande passante Internet dans VC ++? Pourquoi est-ce que je reçois une erreur de l’éditeur de liens avec le pointeur de la fonction template? Comment charger les parameters dans l’application Qt avec QSettings Le constructeur de ” doit explicitement initialiser le membre de référence ” Déclaration optimale des variables en ce qui concerne la scope L’initialisation dans la classe a-t-elle lieu à la compilation ou à l’exécution? Comprendre les macros DEFER et OBSTRUCT Saisissez l’écran Mac OS au format GL_RGB OpenCV – DLL manquante, mais ce n’est pas? Existe-t-il un compilateur C ++ pouvant émettre un avertissement pour une référence en suspens? C ++: impossible de static_cast de double * à int * Au moment de la compilation, générer une séquence entière sans en laisser Simuler le comportement du commutateur dans la spécialisation de modèles

C ++ Numéro tâche du livre

Je suis un débutant en C ++;) Quelle est la qualité du code ci-dessous pour trouver tous les nombres premiers compris entre 2 et 1 000: 

int i, j; for (i=2; i<1000; i++) { for (j=2; j (i/j)) cout << i << " is prime\n"; } }

Vous vous arrêtez quand j = i. Une première optimisation simple consiste à s’arrêter lorsque j = sqrt (i) (puisqu’il ne peut y avoir aucun facteur d’un nombre supérieur à sa racine carrée).

Une mise en œuvre beaucoup plus rapide est par exemple le tamis d’eratosthenes .

Edit: le code semble quelque peu mystérieux, alors voici comment cela fonctionne:

La condition de terminaison sur le for interne est i/j , équivalente à j (ce qui est beaucoup plus clair), car lorsque j==i , nous aurons i/j==0 et le for sera rompu.

La prochaine vérification if(j>(i/j)) est vraiment méchante. Fondamentalement, il vérifie simplement si la boucle a atteint la condition de fin du for (nous avons donc un prime) ou si nous avons atteint la rupture explicite (pas de prime). Si nous touchons la fin du for, alors j==i+1 (pensez-y) => i/j==0 => c'est un nombre premier. Si nous atteignons une pause, cela signifie que j est un facteur de i , mais pas n'importe lequel, le plus petit en fait (puisque nous sortons au premier j qui divise i )! Puisque j est le plus petit facteur, l'autre facteur (ou le produit des facteurs restants, donné par i/j ) sera supérieur ou égal à j , d'où le test. Si j<=i/j , nous frappons une pause et j est le plus petit facteur de i .

C'est du code illisible!

Pas très bien. À mon humble avis, l’indentation et l’espacement sont hideux (aucune infraction). Pour le nettoyer: 

 int i, j; for (i=2; i<1000; i++) { for (j=2; i/j; j++) { if (!(i % j)) break; if (j > i/j) cout << i << " is prime\n"; } }

Cela révèle un bogue: le if (j > i/j) ... doit être à l'extérieur de la boucle interne pour que cela fonctionne. De plus, je pense que la condition i/j est plus déroutante (pour ne pas dire plus lente) que de simplement dire j < i (ou même rien, car une fois que j atteint i , i % j sera 0). Après ces changements, nous avons: 

 int i, j; for (i=2; i<1000; i++) { for (j=2; j < i; j++) { if (!(i % j)) break; } if (j > i/j) cout << i << " is prime\n"; }

Cela marche. Cependant, le j > i/j confond le diable de moi. Je ne peux même pas comprendre pourquoi cela fonctionne (je suppose que je pourrais le comprendre si j'ai passé un moment à ressembler à ce type ). J'écrirais if (j == i) place.

Ce que vous avez mis en œuvre ici s'appelle la division d'essai . Un meilleur algorithme est le tamis d'Eratosthène, comme indiqué dans une autre réponse. Quelques choses à vérifier si vous implémentez un tamis d'Eratosthène:

  1. Ça devrait marcher.
  2. Il ne devrait pas utiliser la division ou le module. Non pas qu'ils soient "mauvais" (bien entendu, ils tendent à être d'un ordre de grandeur plus lent que l'addition, la soustraction, la négation, etc.), mais ils ne sont pas nécessaires, et s'ils sont présents, cela signifie probablement Pas vraiment efficace.
  3. Il devrait être capable de calculer les nombres premiers inférieurs à 10 000 000 en une seconde environ (selon votre matériel, votre compilateur, etc.).

Tout d’abord, votre code est à la fois court et correct, ce qui convient très bien au débutant. 😉

Voici ce que je ferais pour améliorer le code:

1) Définissez les variables à l’intérieur des boucles afin qu’elles ne soient pas confondues avec autre chose. Je voudrais aussi faire de la borne un paramètre ou une constante. 

 #define MAX 1000 for(int i=2;i(i/j)) cout<

2) J'utiliserais le crible d'Eratosthenes , comme l'ont suggéré Joey Adams et Mau. Remarquez que je n'ai pas besoin d'écrire deux fois la borne pour que les deux utilisations soient toujours identiques. 

 #define MAX 1000 bool prime[MAX]; memset(prime, sizeof(prime), true); for(int i=4;i

Les limites sont également à noter. i*i est beaucoup plus rapide que j > i/j et vous n'avez également pas besoin de marquer de nombres

3) Si vous voulez vraiment rendre cet algorithme rapide, vous devez l’optimiser en cache. L'idée est de rechercher d'abord tous les nombres premiers

Vous pouvez également réduire de moitié l'utilisation de l'espace en ne stockant pas les nombres pairs, ce qui signifie que vous n'avez pas à effectuer les calculs pour commencer à travailler sur un nouveau bloc aussi souvent.

Si vous êtes débutant, vous devriez probablement oublier la mémoire cache pour le moment.

La réponse simple à l’ensemble du texte que nous avons posté ici est: Division d’essai ! Si quelqu’un mentionnait les bases mathématiques sur lesquelles cette tâche était basée, nous gagnerions beaucoup de temps;) 

 #include  #define N 1000 int main() { bool primes[N]; for(int i = 0 ; i < N ; i++) primes[i] = false; primes[2] = true; for(int i = 3 ; i < N ; i+=2) { // Check only odd integers bool isPrime = true; for(int j = i/2 ; j > 2 ; j-=2) { // Check only from largest possible multiple of current number if ( j%2 == 0 ) { j = j-1; } // Check only with previous odd divisors if(!primes[j]) continue; // Check only with previous prime divisors if ( i % j == 0 ) { isPrime = false; break; } } primes[i] = isPrime; } return 0; }

Ceci est le code de travail. J’ai également inclus de nombreuses optimisations mentionnées par les précédentes affiches. Si d’autres optimisations peuvent être effectuées, il serait intéressant de savoir.

Cette fonction est plus efficace pour voir si un nombre est premier. 

 bool isprime(const unsigned long n) { if (n<2) return false; if (n<4) return true; if (n%2==0) return false; if (n%3==0) return false; unsigned long r = (unsigned long) sqrt(n); r++; for(unsigned long c=6; c<=r; c+=6) { if (n%(c-1)==0) return false; if (n%(c+1)==0) return false; }