Tester si un nombre est premier

Portrait de trax
Soumis par trax le jeu, 17/01/2008 - 21:05

Calcul de nombres premiers

Petit test de primalité d'un unsigned long long int (sur x86 archi 32bits cela donne un nombre entre 0 et 18446744073709551616). Un exemple de code sera posté, utilisant la librairie gmp pour des nombres plus grands.

Nous utilisons ici la méthode dite "naïve" qui conciste à calculer les modulos successifs de tous les nombres impairs de 3 à la racine du nombre en question, après avoir testé si le nombre est divisible par 2.

#include <stdio.h>
#include <math.h>
 
unsigned long long int primeTest(unsigned long long int nb){
    unsigned long long int racine = (unsigned long long int)(sqrt(nb))+1;
    unsigned long long int i;
    if(nb == 1){
            return 1;
    }
    if((nb % 2) == 0) {
        return 2;
    }
    for (i = 3 ; i < racine ; i+=2){
        if((nb %i) == 0){
            return i;
        }
    }
    return 0;
}
 
int main(void){
    unsigned long long int nb = 3151468321657; 
    unsigned long long int diviseur;
    if((diviseur = primeTest(nb)) == 0){
        printf("Le nombre %lld est premier\n",nb);
    }else{
            printf("Le nombre %lld est divisible par %lld\n", nb, diviseur);
    }
    return 0;
}

A compiler avec la librairie math (-lm) par exemple :

gcc -Wall -lm test.c -o prog -std=gnu99
Domaine: 
Mathématiques

Commentaires

Portrait de coco

Submitted by coco on mer, 20/02/2008 - 20:14.

bah c'est moche !
déjà, déclarer une variable dans l'entête du for, saymal.
en plus ça coute pas grand chose de rajouter un petit test de divisibilité par 2 au début, comme ça on traite tout, waa trop bien.
d'ailleurs il faut aussi vérifier nb!=0 et nb!=1, i.e. nb > 1
et ensuite, il faut mettre un -ansi pour la compilation.

Portrait de furet

Submitted by furet on lun, 28/04/2008 - 10:51.

Déclarer une variable dans l'entête du for "cay pas le mal" si tu es en C99 il aurait peut être mieux valut ajouter -std=gnu99 dans la ligne de compilation de gcc. on se place dans l'hypothèse suivante : Nous faisons l'hypothèse d'un nombre positif non divisible par 2 !!! donc ça veut dire qu'il déjà effectuer un test de divisibilité par 2 avant d'appeler cette fonction. Par contre tester pour 0 et 1 est très juste.
Le -ansi n'est pas obligatoire à moins que tu es envie de faire du C89 (aka ANSI ) pur ; mais dans ce cas tu ne pourra plus utiliser les améliorations apportées par le C99 (le commentaire type //, les for à la java i.e. for(int i =0; testsur_i ; i++) {...}, etc.).

Portrait de trax

Submitted by trax on ven, 02/05/2008 - 22:16.

1. http://www.optic2000.fr/ soit constructif

2B G33K || !2B

2B G33K || !2B

Portrait de coco

Submitted by coco on sam, 03/05/2008 - 10:34.

toi même, c'est fait.

nb : c'est la grosse merde dans les commentaires pour s'y retrouver, je pense qu'un ordre chronologique descendant serait plus approprié.

Portrait de coco

Submitted by coco on lun, 12/05/2008 - 09:30.

trax est repassé derrière, le code est maintenant refaux.
je ne corrigerai pas ce que j'ai déjà corrigé.