Les nombres premiers figurent parmi les objets les plus fascinants et les plus étudiés des mathématiques. Un nombre premier est un entier naturel supérieur à 1 qui ne possède exactement que deux diviseurs naturels distincts : le nombre 1 et lui-même. Contrairement aux nombres composés, qui peuvent être décomposés en plusieurs facteurs, les nombres premiers constituent les véritables « briques de base » de l'arithmétique. En effet, tout entier positif supérieur à 1 peut être représenté comme un produit unique de nombres premiers, propriété fondamentale connue sous le nom de théorème fondamental de l'arithmétique. Depuis l'Antiquité, ces nombres intriguent les mathématiciens par leur répartition apparemment irrégulière au sein de la suite des entiers naturels.
L'étude des nombres premiers a donné naissance à de nombreuses découvertes mathématiques et demeure encore aujourd'hui un domaine de recherche actif. Des savants comme Euclide, Pierre de Fermat ou encore Leonhard Euler ont consacré une partie importante de leurs travaux à comprendre leurs propriétés. Plus récemment, les nombres premiers sont devenus essentiels dans des domaines appliqués tels que la cryptographie moderne, où ils jouent un rôle majeur dans les mécanismes de chiffrement utilisés pour protéger les communications, les transactions bancaires et les données numériques. Ainsi, derrière une notion mathématique apparemment simple se cache une importance pratique considérable.
Du point de vue de la programmation, générer et identifier des nombres premiers constitue un excellent exercice d'algorithmique. Pour déterminer si un entier est premier, il suffit de vérifier qu'il ne possède aucun diviseur autre que 1 et lui-même. Toutefois, effectuer cette vérification naïvement pour chaque nombre peut rapidement devenir coûteux lorsque les valeurs augmentent. Le programme en langage C présenté ci-dessous utilise une méthode plus efficace consistant à rechercher les diviseurs potentiels uniquement jusqu'à la racine carrée du nombre examiné. Cette optimisation réduit considérablement le nombre de calculs nécessaires tout en conservant une grande simplicité de mise en oeuvre.
L'exemple proposé affiche l'ensemble des nombres premiers inférieurs à 1000 et calcule également leur quantité totale. Le résultat montre qu'il existe exactement 168 nombres premiers entre 2 et 999 inclus. Cette démonstration permet non seulement de mieux comprendre la notion de primalité, mais également d'explorer l'utilisation des boucles, des fonctions et des opérations arithmétiques en langage C. Pour les étudiants comme pour les passionnés de mathématiques, ce type de programme constitue une excellente introduction à l'analyse numérique et aux techniques de recherche de nombres premiers, tout en illustrant l'un des concepts les plus célèbres et les plus mystérieux de l'histoire des mathématiques.
A l'aide du code source C suivant, vous trouverez la réponse que vous souhaitez :
Essayer maintenant !
- #include "stdio.h"
- #include "math.h"
-
- int NombreFacteur(int N) {
- int Count=2,I;
- double Racine=sqrt(N);
- for(I=2; I<=Racine;I++) if(N % I == 0) Count++;
- return Count;
- }
-
- int Premier(int N) {
- return (NombreFacteur(N)==2);
- }
-
- int NombrePremierPlusPetit(int N) {
- int Count=0,I;
- for(I=2; I<N; I++) if(Premier(I)) Count++;
- return Count;
- }
-
- void main() {
- int I;
- printf("Liste des nombres premier avant 1000: \n");
- for(I=2; I<1000; I++) if(Premier(I)) printf("%i ",I);
- printf("\nNombre de nombre premier avant 1000: %i",
- NombrePremierPlusPetit(1000));
- }
on obtiendra le résultat suivant :
Liste des nombres premier avant 1000:2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997
Nombre de nombre premier avant 1000: 168