C - déterminer si un nombre est premier
https://stackoverflow.com/questions/1538644
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je suis en train de trouver une méthode qui prend un entier et retourne un booléen dire si le nombre est premier ou non et je ne sais pas beaucoup C; Quelqu'un voudrait-il me donner quelques conseils?
En fait, je ferais cela 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;
}
La solution
OK, donc oubliez C. Supposons que je vous donne un numéro et vous demande de déterminer si elle est premier. Comment faites-vous? Notez les étapes clairement, puis vous soucier de les traduire en code.
Une fois que vous avez l'algorithme déterminé, il sera beaucoup plus facile pour vous de savoir comment écrire un programme, et pour d'autres pour vous aider.
modifier Voici le code C # vous avez publié:
static bool IsPrime(int number) {
for (int i = 2; i < number; i++) {
if (number % i == 0 && i != number) return false;
}
return true;
}
est presque valide C comme il est; il n'y a pas de type bool en C, et pas true ou false, vous devez donc modifier un peu (edit: Kristopher Johnson fait remarquer à juste titre que C99 a ajouté l'en-tête de stdbool.h). Étant donné que certaines personnes n'ont pas accès à un environnement de C99 (! Mais vous devez utiliser un), nous allons faire ce changement très mineur:
int IsPrime(int number) {
int i;
for (i=2; i<number; i++) {
if (number % i == 0 && i != number) return 0;
}
return 1;
}
Ceci est un programme C parfaitement valide qui fait ce que vous voulez. Nous pouvons l'améliorer un peu, sans trop d'effort. Tout d'abord, notez que i est toujours inférieur à number, de sorte que le chèque qui i != number réussit toujours; nous pouvons nous en débarrasser.
En outre, vous ne devez pas vraiment d'essayer tout le chemin diviseurs jusqu'à number - 1; vous pouvez arrêter de vérifier lorsque vous atteignez sqrt (nombre). Depuis sqrt est une opération à virgule flottante et qui apporte un tas de subtilités, nous ne calculons en fait 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 nul, ou une, cette fonction réclamera que le nombre est premier. Vous voulez probablement gérer cela correctement, et vous pouvez faire number non signé, puisque vous êtes plus susceptible de se soucier des valeurs positives seulement:
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;
}
Ceci est certainement pas le moyen le plus rapide pour vérifier si un nombre est premier, mais cela fonctionne, et il est assez simple. Nous avons à peine eu à modifier votre code du tout!
Autres conseils
Je suis surpris que personne n'a mentionné cela.
Détails:
- En gros nombres sont divisibles par secondaires n'a un autre numéro en plus 1 et eux-mêmes
- Par conséquent: un numéro sera secondaires n'a produit de nombres premiers.
Le tamis d'Eratosthène trouve un nombre premier et le stocke. Lorsqu'un nouveau numéro est vérifié pour primeness tous les nombres premiers précédents sont vérifiés sur la base savoir la liste de choix.
Motifs:
- Cet algorithme / problème est connu sous le nom " Embarrassant parallèle "
- Il crée une collection de nombres premiers
- Son exemple d'un problème de programmation dynamique
- Son rapide!
Stephen Canon a répondu très bien!
- L'algorithme peut être encore améliorée en observant que tous les nombres premiers sont de la forme 6k ± 1, à l'exception des 2 et 3.
- Ceci est parce que tous les entiers peuvent être exprimés en tant que (6k + i) pour un entier k et pour i = -1, 0, 1, 2, 3 ou 4; 2 divisions (6k + 0), (6k + 2), (6k + 4); et 3 divisions (6k + 3).
- Donc, une méthode plus efficace consiste à tester si n est divisible par 2 ou 3, puis de vérifier par tous les nombres de la forme 6k ± 1 ≤ √n.
-
Ceci est 3 fois plus vite que 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; } }
- Créer une table de petits nombres premiers, et vérifier si elles se divisent votre numéro d'entrée.
- Si le nombre a survécu à 1, essayer pseudo des tests de primalité avec base de plus en plus. Voir test de Miller-Rabin primalité par exemple.
- Si votre numéro survécu à 2, vous pouvez en conclure qu'il est premier si elle est inférieure à certaines limites bien connues. Dans le cas contraire votre réponse ne sera « probablement prime ». Vous trouverez des valeurs de ces limites dans la page wiki.
ce programme est beaucoup plus efficace pour la vérification d'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<n in for loop
for (int i = 5; i<=sq; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
Vérifier le module de chaque entier de 2 à la racine du numéro que vous vérifiez.
Si le module est alors égal à zéro, il est pas premier.
pseudo-code:
bool IsPrime(int target)
{
for (i = 2; i <= root(target); i++)
{
if ((target mod i) == 0)
{
return false;
}
}
return true;
}
Après avoir lu cette question, je suis intrigué par le fait que certaines réponses proposées optimisation en exécutant une boucle avec des multiples de 2 * 3 = 6.
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 fonctions et la vérification de fois 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
Alors je pensais, ce que quelqu'un gagner trop si généralisé? Je suis venu avec une fonction qui fera un siège d'abord à nettoyer une liste donnée de nombres premiers primordiaux, puis utiliser cette liste pour calculer le plus grand.
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<t; i++)
{
if(n%p[i]==0)
return 0;
qt*=p[i];
}
qt--;
if(n<=qt)
return checkprime(n); /* use another simplified function */
if((q=calloc(qt, sizeof(unsigned long)))==NULL)
{
perror("q=calloc()");
exit(1);
}
for(i=0; i<t; i++)
for(j=p[i]-2; j<qt; j+=p[i])
q[j]=1;
for(j=0; j<qt; j++)
if(q[j])
rt++;
rt=qt-rt;
if((r=malloc(sizeof(unsigned long)*rt))==NULL)
{
perror("r=malloc()");
exit(1);
}
i=0;
for(j=0; j<qt; j++)
if(!q[j])
r[i++]=j+1;
free(q);
sq=ceil(sqrt(n));
for(i=1; i<=sq; i+=qt+1)
{
if(i!=1 && n%i==0)
return 0;
for(j=0; j<rt; j++)
if(n%(i+r[j])==0)
return 0;
}
return 1;
}
Je suppose que je n'optimisez pas le code, mais il est juste. Maintenant, les tests. Parce que tant de mémoire dynamique, je pensais la liste 2 3 5 être un peu plus lent que le 2 3 5 codée en dur. Mais il était ok comme vous pouvez le voir ci-dessous. Après cela, le temps est devenu plus petit et plus petit, culminant la meilleure liste à:
3 5 7 2 11 13 17 19
Avec 8,6 secondes. Donc, si quelqu'un créer un programme hardcoded qui utilise cette technique, je suggère d'utiliser la liste 2 3 et 5, parce que le gain est pas grand. Mais aussi, si prêt à code, cette liste est ok. Le problème est que vous ne pouvez pas dire tous les cas sans boucle, ou votre code serait très grand (Il y aurait 1658879 ORs, qui est || dans la if interne respective). La liste suivante:
3 5 7 2 11 13 17 19 23
le temps a commencé à grossir, avec 13 secondes. Ici tout le test:
$ 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 ne l'ai pas libre (r) intentionnellement, donnant cette tâche à l'OS, comme la mémoire sera libérée dès que le programme est sorti, pour gagner du temps. Mais il serait sage de le libérer si vous avez l'intention de continuer à courir votre code après le calcul.
BONUS
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;
}
Heure:
$ time ./testprimebool.x 18446744065119617029 7
h(2,3,5,7)
Yes, its prime.
real 0m9.123s
user 0m9.132s
sys 0m0.000s
Je voudrais juste ajouter qu'aucun nombre pair (bar 2) peut être un nombre premier. Il en résulte une autre condition préalable à boucle. Ainsi, le code final 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;
}
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<val)
{
if (val % div == 0) return FALSE; /* evenly divisible */
div+=2;
square=div*div;
}
if (square==val) return FALSE;
return TRUE;
}
Manipulation de 2 et les nombres pairs sont conservés hors de la boucle principale qui ne traite que des nombres impairs divisés en nombres impairs. En effet, un nombre impair modulo un nombre pair sera toujours donner une réponse non-zéro, ce qui rend ces tests redondants. Ou, pour le mettre une autre façon, 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 vraiment coûteuse sur l'architecture x86 bien comment varie coûteux (voir http: //gmplib.org/~tege/x86-timing.pdf ). Multiplications d'autre part sont tout à fait pas cher.
Utilisation d'Eratosthène Sieve, le calcul est assez rapide à comparer « connu dans le » algorithme de choix de nombres.
En utilisant pseudocode à partir de son wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), je serai en mesure d'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.
NOTE : la valeur peut varier dépendent des spécifications matérielles
. Utilisez for (i = 2; i <= number/i; i++) pour limiter les itérations.
number%i, number/i est efficace sur de nombreux compilateurs comme les calculs du quotient et le reste sont fait ensemble, donc encourir sans frais supplémentaires pour faire les deux contre seulement 1.
Une solution très simple:
bool IsPrime(unsigned number) {
for(unsigned i = 2; i <= number/i; i++){
if(number % i == 0){
return false;
}
}
return number >= 2;
}
