C - déterminer si un nombre est premier

Question

J'essaie de trouver une méthode qui prend un entier et renvoie un booléen pour dire si le nombre est premier ou non et je ne connais pas grand-chose au C ; quelqu'un pourrait-il me donner quelques conseils ?

En gros, 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;
}

Answer 1

OK, oubliez C. Supposons que je vous donne un nombre et que je vous demande de déterminer s'il est premier. Comment vous y prenez-vous ? Écrivez clairement les étapes, puis se soucier de les traduire en code.

Une fois l'algorithme déterminé, il sera beaucoup plus facile pour vous de trouver comment écrire un programme, et pour les autres de vous aider.

éditer : 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;
}

C'est très près C valide tel quel ; il n'y a pas de bool en C, et aucun true ou false Il faut donc le modifier un peu (edit : Kristopher Johnson signale correctement que C99 a ajouté l'en-tête stdbool.h). Puisque certaines personnes n'ont pas accès à un environnement C99 (mais vous devriez en utiliser un !), faisons 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;
}

C'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 donc la vérification que i != number réussit toujours ; on peut s'en débarrasser.

De plus, vous n'avez pas besoin d'essayer des 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 cela apporte tout un tas 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 affirmera que le nombre est premier. Vous voudrez probablement gérer cela correctement, et vous voudrez peut-être faire en sorte que la fonction number sont non signées, car il est plus probable que vous ne vous souciiez 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 la façon la plus rapide de vérifier si un nombre est premier, mais cela fonctionne, et c'est assez simple. Nous avons à peine eu à modifier votre code !

Answer 2

Je suis surpris que personne ne l'ait mentionné.

Utilisez le Le tamis d'Eratosthène

Détails :

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

Le tamis d'Eratosthène trouve un nombre premier et le stocke. Lorsqu'on vérifie la primarité d'un nouveau nombre, tous les nombres premiers précédents sont comparés à la liste des nombres premiers connus.

Raisons :

1. Cet algorithme/problème est connu sous le nom de " Un parallèle embarrassant "
2. Il crée une collection de nombres premiers
3. C'est un exemple de problème de programmation dynamique
4. C'est rapide !

Answer 3

1. Construisez une table de petits nombres premiers, et vérifiez s'ils divisent votre nombre d'entrée.
2. Si le nombre a survécu à 1, essayez les tests de pseudo primalité avec une base croissante. Voir Test de primauté de Miller-Rabin par exemple.
3. Si votre nombre survient à 2, vous pouvez conclure qu'il est premier s'il est inférieur à certaines limites bien connues. Sinon, votre réponse sera seulement "probablement premier". Vous trouverez quelques valeurs pour ces limites dans la page wiki.

Answer 4

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

Si le module est égal à zéro, alors il n'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;
}

Answer 5

J'ajouterais simplement qu'aucun nombre pair (barre 2) ne peut être un nombre premier. Cela entraîne une autre condition avant la boucle for. 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;
}