C – déterminer si un nombre est premier

J’essaie de trouver une méthode qui prend un entier et retourne un booléen pour dire si le nombre est premier ou non et je ne connais pas beaucoup C; quelqu’un voudrait-il me donner des conseils?

En gros, je ferais ceci en C # comme ceci:

static bool IsPrime(int number) { for (int i = 2; i < number; i++) { if (number % i == 0 && i != number) return false; } return true; } 

OK, alors oubliez C. Supposons que je vous donne un chiffre et vous demande de déterminer si c’est premier. Comment faites-vous? Notez clairement les étapes, puis inquiétez-vous de les traduire en code.

Une fois que l’algorithme est déterminé, il vous sera beaucoup plus facile de comprendre comment écrire un programme, et d’autres personnes pourront vous aider.

edit: Voici le code C # que vous avez posté:

 static bool IsPrime(int number) { for (int i = 2; i < number; i++) { if (number % i == 0 && i != number) return false; } return true; } 

Ceci est presque valable C tel quel; il n'y a pas de type bool dans C, ni true ni false , vous devez donc le modifier un peu (edit: Kristopher Johnson souligne à juste titre que C99 a ajouté l'en-tête stdbool.h). Étant donné que certaines personnes n'ont pas access à un environnement C99 (mais vous devriez en utiliser un!), Apportons ce changement très mineur:

 int IsPrime(int number) { int i; for (i=2; i 

Ceci est un programme C parfaitement valide qui fait ce que vous voulez. Nous pouvons l'améliorer un peu sans trop d'effort. Premièrement, notez que i est toujours inférieur au number , donc vérifiez que i != number réussit toujours; nous pouvons nous en débarrasser.

En outre, vous n'avez pas besoin d'essayer les diviseurs jusqu'au number - 1 ; vous pouvez arrêter de vérifier lorsque vous atteignez sqrt (nombre). Puisque sqrt est une opération à virgule flottante qui apporte toute une stack de subtilités, nous ne calculerons pas réellement sqrt(number) . Au lieu de cela, nous pouvons simplement vérifier que i*i <= number :

 int IsPrime(int number) { int i; for (i=2; i*i<=number; i++) { if (number % i == 0) return 0; } return 1; } 

Une dernière chose, cependant; il y avait un petit bug dans votre algorithme original! Si number est négatif, ou zéro, ou un, cette fonction prétendra que le nombre est premier. Vous souhaiterez probablement gérer cela correctement, et vous souhaiterez peut-être que le number soit pas signé, car vous êtes plus susceptible de ne vous soucier que des valeurs positives:

 int IsPrime(unsigned int number) { if (number <= 1) return 0; // zero and one are not prime unsigned int i; for (i=2; i*i<=number; i++) { if (number % i == 0) return 0; } return 1; } 

Ce n'est certainement pas le moyen le plus rapide de vérifier si un nombre est premier, mais cela fonctionne, et c'est assez simple. Nous avons à peine dû modifier votre code du tout!

Je suis surpris que personne n’ait mentionné cela.

Utilisez le tamis des ératosthènes

Détails:

  1. Fondamentalement, les numéros non-prime sont divisibles par un autre nombre que 1 et eux-mêmes
  2. Par conséquent: un numéro non-prix sera un produit de nombres premiers.

Le tamis d’Eratosthène trouve un nombre premier et le stocke. Lorsqu’un nouveau nombre est vérifié pour la primauté, tous les nombres premiers précédents sont comparés à la liste des nombres premiers connus.

Les raisons:

  1. Cet algorithme / problème est appelé ” Parallèlement gênant ”
  2. Il crée une collection de nombres premiers
  3. C’est un exemple de problème de programmation dynamic
  4. C’est rapide!

Stephen Canon a très bien répondu!

Mais

  • L’algorithme peut être amélioré en observant que tous les nombres premiers sont de la forme 6k ± 1, à l’exception de 2 et 3.
  • En effet, tous les entiers peuvent être exprimés sous la forme (6k + i) pour un entier k et pour i = −1, 0, 1, 2, 3 ou 4; 2 divise (6k + 0), (6k + 2), (6k + 4); et 3 divisions (6k + 3).
  • Une méthode plus efficace consiste donc à tester si n est divisible par 2 ou 3, puis à vérifier tous les nombres de forme 6k ± 1 ≤ √n.
  • C’est 3 fois plus rapide que de tester tous les m jusqu’à √n.

     int IsPrime(unsigned int number) { if (number <= 3 && number > 1) return 1; // as 2 and 3 are prime else if (number%2==0 || number%3==0) return 0; // check if number is divisible by 2 or 3 else { unsigned int i; for (i=5; i*i<=number; i+=6) { if (number % i == 0 || number%(i + 2) == 0) return 0; } return 1; } } 
  1. Construisez une table de petits nombres premiers et vérifiez s’ils divisent votre numéro d’entrée.
  2. Si le nombre a survécu à 1, essayez les tests de pseudo-primalité avec une base croissante. Voir le test de primalité Miller-Rabin par exemple.
  3. Si votre nombre a survécu jusqu’à 2, vous pouvez en conclure qu’il est premier s’il est inférieur à des limites bien connues. Sinon, votre réponse ne sera que “probablement prioritaire”. Vous trouverez des valeurs pour ces bornes dans la page wiki.

Ce programme est très efficace pour vérifier un numéro unique pour le contrôle de primalité.

 bool check(int n){ if (n <= 3) { return n > 1; } if (n % 2 == 0 || n % 3 == 0) { return false; } int sq=sqrt(n); //include math.h or use i*i 

Vérifiez le module de chaque entier de 2 à la racine du nombre que vous vérifiez.

Si le module est égal à zéro, ce n’est pas un nombre premier.

pseudo code:

 bool IsPrime(int target) { for (i = 2; i <= root(target); i++) { if ((target mod i) == 0) { return false; } } return true; } 

J’appendais simplement qu’aucun nombre pair (barre 2) ne peut être un nombre premier. Cela entraîne une autre condition avant la boucle. Donc, le code de fin devrait ressembler à ceci:

 int IsPrime(unsigned int number) { if (number <= 1) return 0; // zero and one are not prime if ((number > 2) && ((number % 2) == 0)) return 0; //no even number is prime number (bar 2) unsigned int i; for (i=2; i*i<=number; i++) { if (number % i == 0) return 0; } return 1; } 

Après avoir lu cette question, j’ai été insortinggué par le fait que certaines réponses offraient une optimisation en exécutant une boucle avec des multiples de 2 * 3 = 6.

Donc, je crée une nouvelle fonction avec la même idée, mais avec des multiples de 2 * 3 * 5 = 30.

 int check235(unsigned long n) { unsigned long sq, i; if(n<=3||n==5) return n>1; if(n%2==0 || n%3==0 || n%5==0) return 0; if(n<=30) return checkprime(n); /* use another simplified function */ sq=ceil(sqrt(n)); for(i=7; i<=sq; i+=30) if (n%i==0 || n%(i+4)==0 || n%(i+6)==0 || n%(i+10)==0 || n%(i+12)==0 || n%(i+16)==0 || n%(i+22)==0 || n%(i+24)==0) return 0; return 1; } 

En exécutant les deux fonctions et en vérifiant les temps, je pourrais affirmer que cette fonction est vraiment plus rapide. Permet de voir 2 tests avec 2 nombres premiers différents:

 $ time ./testprimebool.x 18446744069414584321 0 f(2,3) Yes, its prime. real 0m14.090s user 0m14.096s sys 0m0.000s $ time ./testprimebool.x 18446744069414584321 1 f(2,3,5) Yes, its prime. real 0m9.961s user 0m9.964s sys 0m0.000s $ time ./testprimebool.x 18446744065119617029 0 f(2,3) Yes, its prime. real 0m13.990s user 0m13.996s sys 0m0.004s $ time ./testprimebool.x 18446744065119617029 1 f(2,3,5) Yes, its prime. real 0m10.077s user 0m10.068s sys 0m0.004s 

Donc, je pensais que quelqu'un gagnerait trop s'il était généralisé? Je suis venu avec une fonction qui va faire un siège en premier pour nettoyer une liste donnée de nombres premiers primordiaux, puis utiliser cette liste pour calculer la plus grande.

 int checkn(unsigned long n, unsigned long *p, unsigned long t) { unsigned long sq, i, j, qt=1, rt=0; unsigned long *q, *r; if(n<2) return 0; for(i=0; i 

Je suppose que je n'ai pas optimisé le code, mais c'est juste. Maintenant, les tests. Parce que tant de mémoire dynamic, je m'attendais à ce que la liste 2 3 5 soit un peu plus lente que la 2 3 5 codée en dur. Mais ça allait comme tu peux le voir ci-dessous. Après cela, le temps est devenu de plus en plus petit, aboutissant à la meilleure liste pour être:

2 3 5 7 11 13 17 19

Avec 8,6 secondes Donc, si quelqu'un créait un programme codé en dur utilisant une telle technique, je suggérerais d'utiliser la liste 2 3 et 5, car le gain n'est pas si grand. Mais aussi, si vous voulez coder, cette liste est correcte. Le problème est que vous ne pouvez pas énoncer tous les cas sans boucle, ou votre code serait très gros (il y aurait 1658879 ORs , c'est-à-dire || dans les if internes respectifs). La liste suivante:

2 3 5 7 11 13 17 19 23

le temps a commencé à grossir, avec 13 secondes. Voici le test complet:

 $ time ./testprimebool.x 18446744065119617029 2 3 5 f(2,3,5) Yes, its prime. real 0m12.668s user 0m12.680s sys 0m0.000s $ time ./testprimebool.x 18446744065119617029 2 3 5 7 f(2,3,5,7) Yes, its prime. real 0m10.889s user 0m10.900s sys 0m0.000s $ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 f(2,3,5,7,11) Yes, its prime. real 0m10.021s user 0m10.028s sys 0m0.000s $ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 f(2,3,5,7,11,13) Yes, its prime. real 0m9.351s user 0m9.356s sys 0m0.004s $ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17 f(2,3,5,7,11,13,17) Yes, its prime. real 0m8.802s user 0m8.800s sys 0m0.008s $ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17 19 f(2,3,5,7,11,13,17,19) Yes, its prime. real 0m8.614s user 0m8.564s sys 0m0.052s $ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17 19 23 f(2,3,5,7,11,13,17,19,23) Yes, its prime. real 0m13.013s user 0m12.520s sys 0m0.504s $ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17 19 23 29 f(2,3,5,7,11,13,17,19,23,29) q=calloc(): Cannot allocate memory 

PS Je n'ai pas libéré (r) intentionnellement, donnant cette tâche à l'OS, car la mémoire serait libérée dès que le programme serait terminé, pour gagner du temps. Mais il serait sage de le libérer si vous avez l’intention de continuer à exécuter votre code après le calcul.


PRIME

 int check2357(unsigned long n) { unsigned long sq, i; if(n<=3||n==5||n==7) return n>1; if(n%2==0 || n%3==0 || n%5==0 || n%7==0) return 0; if(n<=210) return checkprime(n); /* use another simplified function */ sq=ceil(sqrt(n)); for(i=11; i<=sq; i+=210) { if(n%i==0 || n%(i+2)==0 || n%(i+6)==0 || n%(i+8)==0 || n%(i+12)==0 || n%(i+18)==0 || n%(i+20)==0 || n%(i+26)==0 || n%(i+30)==0 || n%(i+32)==0 || n%(i+36)==0 || n%(i+42)==0 || n%(i+48)==0 || n%(i+50)==0 || n%(i+56)==0 || n%(i+60)==0 || n%(i+62)==0 || n%(i+68)==0 || n%(i+72)==0 || n%(i+78)==0 || n%(i+86)==0 || n%(i+90)==0 || n%(i+92)==0 || n%(i+96)==0 || n%(i+98)==0 || n%(i+102)==0 || n%(i+110)==0 || n%(i+116)==0 || n%(i+120)==0 || n%(i+126)==0 || n%(i+128)==0 || n%(i+132)==0 || n%(i+138)==0 || n%(i+140)==0 || n%(i+146)==0 || n%(i+152)==0 || n%(i+156)==0 || n%(i+158)==0 || n%(i+162)==0 || n%(i+168)==0 || n%(i+170)==0 || n%(i+176)==0 || n%(i+180)==0 || n%(i+182)==0 || n%(i+186)==0 || n%(i+188)==0 || n%(i+198)==0) return 0; } return 1; } 

Temps:

 $ time ./testprimebool.x 18446744065119617029 7 h(2,3,5,7) Yes, its prime. real 0m9.123s user 0m9.132s sys 0m0.000s 
 int is_prime(int val) { int div,square; if (val==2) return TRUE; /* 2 is prime */ if ((val&1)==0) return FALSE; /* any other even number is not */ div=3; square=9; /* 3*3 */ while (square 

Le traitement des nombres pairs et 2 est exclu de la boucle principale et ne traite que les nombres impairs divisés par des nombres impairs. En effet, un nombre impair modulo un nombre pair donnera toujours une réponse non nulle, ce qui rend ces tests redondants. Ou, pour le dire autrement, un nombre impair peut être divisible par un autre nombre impair, mais jamais par un nombre pair (E * E => E, E * O => E, O * E => E et O * O => O).

Une division / module est très onéreux pour l'architecture x86, mais son coût varie (voir http://gmplib.org/~tege/x86-timing.pdf ). Les multiplications par contre sont très bon marché.

En utilisant Sieve of Eratosthenes, le calcul est assez rapide comparé à l’algorithme des nombres premiers “connus”.

En utilisant le pseudocode de son wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ), je pourrai avoir la solution sur C #.

 public bool IsPrimeNumber(int val) { // Using Sieve of Eratosthenes. if (val < 2) { return false; } // Reserve place for val + 1 and set with true. var mark = new bool[val + 1]; for(var i = 2; i <= val; i++) { mark[i] = true; } // Iterate from 2 ... sqrt(val). for (var i = 2; i <= Math.Sqrt(val); i++) { if (mark[i]) { // Cross out every i-th number in the places after i (all the multiples of i). for (var j = (i * i); j <= val; j += i) { mark[j] = false; } } } return mark[val]; } 

IsPrimeNumber (1000000000) prend 21s 758ms.

REMARQUE : La valeur peut varier en fonction des spécifications du matériel.