{"id":87,"date":"2012-03-31T21:13:37","date_gmt":"2012-03-31T20:13:37","guid":{"rendered":"http:\/\/www.unicoda.com\/?p=87"},"modified":"2012-11-19T15:32:32","modified_gmt":"2012-11-19T14:32:32","slug":"algorithme-de-recherche-des-nombres-premiers","status":"publish","type":"post","link":"https:\/\/www.unicoda.com\/?p=87","title":{"rendered":"Algorithme de recherche des nombres premiers"},"content":{"rendered":"<p><a href=\"http:\/\/www.unicoda.com\/?attachment_id=98\" rel=\"attachment wp-att-98\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-medium wp-image-98\" title=\"Nombres Premiers\" src=\"http:\/\/www.unicoda.com\/wp-content\/uploads\/2012\/03\/Science-et-Vie-Les-nombres-premiers-et-les-electrons-300x300.jpg\" alt=\"\" width=\"300\" height=\"300\" srcset=\"https:\/\/www.unicoda.com\/wp-content\/uploads\/2012\/03\/Science-et-Vie-Les-nombres-premiers-et-les-electrons-300x300.jpg 300w, https:\/\/www.unicoda.com\/wp-content\/uploads\/2012\/03\/Science-et-Vie-Les-nombres-premiers-et-les-electrons-150x150.jpg 150w, https:\/\/www.unicoda.com\/wp-content\/uploads\/2012\/03\/Science-et-Vie-Les-nombres-premiers-et-les-electrons.jpg 392w\" sizes=\"auto, (max-width: 300px) 85vw, 300px\" \/><\/a><\/p>\n<p>Aujourd&rsquo;hui, nous nous int\u00e9ressons aux nombres premiers et \u00e0 la fa\u00e7on de les trouver. Pour cela, voil\u00e0 un algorithme assez simple qui permet de trouver un nombre n de nombre premier. Dans sa premi\u00e8re version, l&rsquo;algorithme recommen\u00e7ait \u00e0 calculer \u00e0 partir de 5 (si ma m\u00e9moire est bonne ;) ) \u00e0 chaque ex\u00e9cution. Dans sa version actuelle, nous pouvons maintenant reprendre les calculs \u00e0 partir du dernier nombre premier trouv\u00e9. Quelques am\u00e9liorations pourront n\u00e9anmoins \u00eatre apporter comme la possibilit\u00e9 d&rsquo;interrompre le programme alors qu&rsquo;il teste des nombres et de le relancer sans avoir \u00e0 repartir du dernier nombre premier, la gestion des grands nombres pourrait \u00eatre \u00e0 revoir. Nous pouvons \u00e9galement envisager la division du fichier contenant les nombres premiers en plusieurs autres fichiers tous les x nombres.<\/p>\n<p>L&rsquo;algorithme est pr\u00e9sent\u00e9 en code C et repose sur ce que mon professeur de s\u00e9curit\u00e9 d\u00e9signait il y a quelques jours comme la \u00ab\u00a0m\u00e9thode na\u00efve\u00a0\u00bb; puisqu&rsquo;il existe d&rsquo;autres m\u00e9thodes, permettant de s&rsquo;assurer qu&rsquo;un nombre n&rsquo;est pas premier entre autres (mais pas d&rsquo;\u00e9quivalence ici, si le nombre n&rsquo;est pas premier, le th\u00e9or\u00e8me ne permet pas de monter qu&rsquo;il l&rsquo;est) et dont je parlerais certainement dans un autre article.<\/p>\n<p>Au jour d&rsquo;aujourd&rsquo;hui, notre fichier fait 969\u00a0376\u00a0620 octets et est trop grand pour \u00eatre ouvert par certains \u00e9diteur de texte :D.\u00a0 Pour d\u00e9terminer si un nombre est premier, l&rsquo;algorithme va regarder le r\u00e9sultat de la division du nombre test\u00e9 par les nombres premiers d\u00e9j\u00e0 pr\u00e9sent dans le fichier. Si le reste vaut 0, le nombre test\u00e9 est divisible par un autre nombre que 1 ou lui-m\u00eame, il n&rsquo;est donc pas premier. On peut arr\u00eater ce test, lorsque le nombre premier utilis\u00e9 dans la division euclidienne est sup\u00e9rieur \u00e0 la racine carr\u00e9 du nombre test\u00e9 et ainsi gagner du temps. De m\u00eame, l&rsquo;incr\u00e9mentation des nombres test\u00e9s de 2 en 2 \u00e0 partir d&rsquo;un entier impair permet de ne jamais tester les nombres pairs puisque nous les savons tous divisibles par 2. Le lien vers un dossier contenant le code et les fichiers qu&rsquo;il utilise: <a href=\"http:\/\/www.unicoda.com\/?attachment_id=93\" rel=\"attachment wp-att-93\">Algorithme Nombres Premiers<\/a>. Place maintenant au programme:<\/p>\n<pre>#include &lt;stdio.h&gt;\r\n#include &lt;stdlib.h&gt;\r\n#include &lt;math.h&gt;\r\n\r\nint premier(int test);\r\n\r\nint main(void)\r\n{\r\n\u00a0\u00a0 \u00a0\/*VARIABLE:\r\n\u00a0\u00a0 \u00a0\u00a0 recherche: le nombre de nombre premier \u00e0 rechercher\r\n\u00a0\u00a0 \u00a0\u00a0 dernier: le dernier nombre test\u00e9\r\n        lors de l'appel pr\u00e9c\u00e9dent au programme,\r\n       \u00a0contenu dans dernier.txt*\/\r\n\r\n\u00a0\u00a0 \u00a0int recherche, dernier;\r\n\u00a0\u00a0 \u00a0FILE *fichier_dernier_nbr;\r\n\u00a0\u00a0 \u00a0FILE\u00a0 *fichier;\r\n\u00a0\u00a0 \u00a0recherche=100;\r\n\u00a0\u00a0 \u00a0dernier=0;\r\n\r\n\u00a0\u00a0 \u00a0\/*Initialisation du dernier nombre test\u00e9\r\n\u00a0\u00a0 \u00a0\u00a0 dernier est obligatoirement impair*\/\r\n\u00a0\u00a0 \u00a0fichier=NULL;\r\n\u00a0\u00a0 \u00a0fichier_dernier_nbr = NULL;\r\n\u00a0\u00a0\u00a0 fichier_dernier_nbr = fopen(\"dernier.txt\", \"r+\");\r\n\r\n\u00a0\u00a0\u00a0 if (fichier_dernier_nbr != NULL)\r\n\u00a0\u00a0\u00a0 {\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 fscanf(fichier_dernier_nbr, \"%d\", &amp;dernier);\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 fclose(fichier_dernier_nbr);\r\n\u00a0\u00a0\u00a0 }\r\n\r\n\u00a0\u00a0 \u00a0\/*On recherche autant de nombre premier\r\n       que le contenu de recherche*\/\r\n\u00a0\u00a0 \u00a0while(recherche&gt;0)\r\n\u00a0\u00a0 \u00a0{\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0if(premier(dernier))\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0{\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\/*Le nombre test\u00e9 est premier*\/\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\/*printf(\"%d:Premier\\n\", dernier);*\/\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\/*On enregistre le nombre \u00e0 la fin du fichier*\/\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0fichier = fopen(\"test.txt\", \"r+\");\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0fseek(fichier, 0, SEEK_END);\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0fprintf(fichier, \"%d\\n\", dernier);\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0fclose(fichier);\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\/*On d\u00e9cr\u00e9mente le nombre de nombre premier\r\n              encore \u00e0 trouver*\/\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0recherche--;\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0}\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0dernier=dernier+2;\r\n\u00a0\u00a0 \u00a0}\r\n\u00a0\u00a0 \u00a0\/*On enregistre le dernier \u00e0 la fin du fichier*\/\r\n\u00a0\u00a0 \u00a0fichier = fopen(\"dernier.txt\", \"w+\");\r\n\u00a0\u00a0 \u00a0fseek(fichier, 0, SEEK_SET);\r\n\u00a0\u00a0 \u00a0fprintf(fichier, \"%d\", dernier);\r\n\u00a0\u00a0 \u00a0fclose(fichier);\r\n\r\n\u00a0\u00a0 \u00a0printf(\"Operation effectuee avec succes.\\n\");\r\n\r\n\u00a0\u00a0 \u00a0return EXIT_SUCCESS;\r\n}\r\n\r\n\/*Renvoi 1 si le nombre est un nombre premier*\/\r\nint premier(int test)\r\n{\r\n\u00a0\u00a0 \u00a0int nb_premier;\r\n\u00a0\u00a0 \u00a0int borne=0;\r\n\r\n\u00a0\u00a0 \u00a0FILE* fichier = NULL;\r\n\u00a0\u00a0\u00a0 fichier = fopen(\"test.txt\", \"r+\");\r\n\r\n\u00a0\u00a0\u00a0 if (fichier != NULL)\r\n\u00a0\u00a0\u00a0 {\r\n\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 while(feof(fichier)==0 &amp;&amp; borne==0)\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0{\u00a0\u00a0 \u00a0\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0fscanf(fichier, \"%d\", &amp;nb_premier);\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\/*printf(\"%d\\n\", nb_premier);*\/\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\/*Nombre divisible par un nombre premier,\r\n              premier(test)=0*\/\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0if(test%nb_premier==0)\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0{\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0fclose(fichier);\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0return 0;\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0}\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\/*Si la racine carr\u00e9 du nombre test\u00e9 est inf\u00e9rieure au\r\n              nombre premier actuel,inutile de continuer le test*\/\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0if(nb_premier&gt;sqrt(test))\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0{borne=1;}\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0}\r\n\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 fclose(fichier);\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0if(borne==1)\r\n\u00a0\u00a0 \u00a0\u00a0\u00a0 \u00a0{return 1;}\r\n\u00a0\u00a0 \u00a0}\r\n\u00a0\u00a0 \u00a0return 0;\r\n}<\/pre>\n<p>Illustration: <em>illustrer.fr<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Aujourd&rsquo;hui, nous nous int\u00e9ressons aux nombres premiers et \u00e0 la fa\u00e7on de les trouver. Pour cela, voil\u00e0 un algorithme assez simple qui permet de trouver un nombre n de nombre premier. Dans sa premi\u00e8re version, l&rsquo;algorithme recommen\u00e7ait \u00e0 calculer \u00e0 partir de 5 (si ma m\u00e9moire est bonne ;) ) \u00e0 chaque ex\u00e9cution. Dans sa &hellip; <a href=\"https:\/\/www.unicoda.com\/?p=87\" class=\"more-link\">Continuer la lecture<span class=\"screen-reader-text\"> de &laquo;&nbsp;Algorithme de recherche des nombres premiers&nbsp;&raquo;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[48],"class_list":["post-87","post","type-post","status-publish","format-standard","hentry","category-code","tag-algorithme"],"_links":{"self":[{"href":"https:\/\/www.unicoda.com\/index.php?rest_route=\/wp\/v2\/posts\/87","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.unicoda.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.unicoda.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.unicoda.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.unicoda.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=87"}],"version-history":[{"count":19,"href":"https:\/\/www.unicoda.com\/index.php?rest_route=\/wp\/v2\/posts\/87\/revisions"}],"predecessor-version":[{"id":103,"href":"https:\/\/www.unicoda.com\/index.php?rest_route=\/wp\/v2\/posts\/87\/revisions\/103"}],"wp:attachment":[{"href":"https:\/\/www.unicoda.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=87"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.unicoda.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=87"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.unicoda.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=87"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}