K6 Passion : Les nombres premiers

J’ai une passion bizarre pour les nombres premiers.
Dans les cas (assez fréquents) où ça ne va pas ou quand je suis dans une situation stressante j’ai tendance à me répéter la liste des nombres premiers de 0 à 100.
C’est un truc que je fais depuis quelques années.

Et comme ça n’allait pas dernièrement je me suis amusée à faire une sorte de crible de nombres premiers.
A part pour la première dizaine je n’ai testé que les nombre qui se terminent par les chiffres 1, 3, 7 ou 9. Les nombres pairs (qui se terminent par 0, 2, 4, 6, 8) étant par définition des multiples évidents de 2, de même les nombres qui se terminent par 5 (et 0 mais je les déjà éliminés car pairs) sont des multiples de 5.
Ensuite pour beaucoup j’ai fait de tête mais plus je suis allée loin et plus je suis allée vers une méthode de crible pure (pour gagner du temps).
Pour les multiples de 3 c’est simple, pour la seconde dizaine (de 10 à 19) il n’y a aucun nombre a tester, les multiples de 3 sont 12 – déjà éliminé car pair, 15 – déjà éliminé car multiple évident de 5 et 18 – pareil c’est pair donc déjà éliminé. Pour la troisième dizaine (20 à 29) on va voir que 21 = 3 x 7 (ça normalement on le sait déjà) et comme 27 = 21 + 6 on va voir que c’est aussi un multiple de 3 (même si on le sait déjà). Pour la quatrième dizaine (30 à 39), pareil on a 33 = 3 x 11 (= 27 + 6) et 39 = 3 x 13 (= 33 + 6).
Alors ce que je dis là est très basiques, vous allez me dire que vous savez bien que 21, 27, 33 ou 39 sont des multiples de 3. En plus vous vous souvenez qu’en additionnant les chiffres qui composent un nombre, si le résultat donne un multiple de 3 alors le nombre est un multiple de 3. Mais c’est pour expliquer une méthode.
Pour les multiples de 3 quand on arrive à la cinquième dizaine (de 40 à 49) je ne réfléchis qu’à peine. En effet on va avoir 42 (= 12 + 30), 45 (= 15 + 30) et 48 (= 18 + 30) et comme ça, de proche en proche, je vais éliminer tous les multiples de 3 et trouver facilement leur décompositions en facteur de nombres premiers.
J’emploie la même méthode pour les multiples de 7. Je ne commence à tester les nombres pour voir s’ils sont multiples de 7 qu’à partir de 49 (= 7²), les multiples de 7 inférieurs à 49 sont déjà éliminés car ils sont aussi multiples de nombres inférieurs à 7, déjà testés ou éliminés directement. Et de proche en proche en additionnant 14 à chaque fois j’élimine progressivement le multiples de 7.
Pareil avec 11 (à partir de 121), 13 (à partir de 169), 17 (à partir de 289), 19 (à partir de 361), 23 (à partir de 529), 29 (à partir de 841) et il ne me reste qu’à éliminer 961 (= 31²) pour en avoir fini avec mon crible des nombres premiers de 0 à 1000.
Et j’aurais pu continuer longtemps comme cela mais on voit que plus on va loin et plus on aura de tests à faire.

J’ai aussi un petit jeu avec les nombres premiers, j’essaie de déterminer de tête s’ils sont premiers et sinon quelle est leur décomposition en facteurs de nombres premiers.
J’y arrive bien avec les nombres inférieurs à 1000, pour ceux entre 1000 et 10000 je me perds un peu plus facilement mais j’essaie.
Voici la méthode que j’utilise avec l’exemple de 659 (tiré aléatoirement aux dés 10) :

  • Est-il multiple de 2 ?
    Je vérifie s’il est pair (multiple de 2), ce n’est pas le cas donc je passe au test suivant.
  • Est-il multiple de 3 ?
    6 + 5 + 9 = 20, 20 n’est pas un multiple de 3 donc 659 n’est pas un multiple de 3.
  • Est-il multiple de 5 ?
    659 ne se termine ni par un 5 ni par un 0 donc il n’est pas un multiple de 5.
  • Est-il multiple de 7 ?
    C’est là que je commence à utiliser une méthode de calcul que je vais utiliser par la suite. Je sais déjà que 659 n’est ni multiple de 2, ni de 3, ni même de 5.
    659 se termine par un 9, je cherche un multiple de 7 que je connais qui se termine par un 9 et je sais que 7 x 7 = 49.
    Je fais alors 659 – 49 = 610 et je teste si 61 est multiple de 7. Comme je sais que 61 est premier (je connais la liste de 0 à 100 par cœur) j’en déduis que 659 n’est pas un multiple de 7.
    Alors pour les gens qui n’auraient pas compris ce que je fais là je vais essayer de détailler un peu, vous allez voir c’est tout simple.
    Si 659 était multiple de 7 on pourrait l’écrire 7 x q (q pour quelque chose que je ne connais pas encore).
    Toujours à supposer que 659 soit multiple de 7 :

    • Quand je fais 659 – 49 = 610 je fais 7 x q – 7 x 7 = 7 x (q – 7) ce qui veut dire que 610 devrait être multiple de 7 car on peut l’écrire 7 x (q – 7).
    • Un peu sur le même principe je teste 61 plutôt que 610 car si on suppose que 61 est multiple de 7 et qu’on peut l’écrire 61 = 7 x k (k pour kuelkue chose) alors on peut écrire 610 = 10 x 7 x k = 7 x (10 x k) donc 610 serait multiple de 7.
    • Comme 61 n’est pas multiple de 7 le château de carte s’écroule, 610 n’est pas multiple de 7 et 659 ne peut pas non plus être un multiple de 7.
  • Comme il n’est pas multiple de 7 est-ce que 659 est multiple de 11 ?
    Même méthode, je commence par faire 659 – 99 = 560 (car 99 = 11 x 9) puis je vois si 56 = 2³ x 7, ça n’est pas un multiple de 11, donc 659 n’est pas multiple de 11.
  • On passe au test pour voir s’il est multiple de 13.
    Je sais que 3 x 3 = 9 donc je vais commencer par retirer 13 x 3 = 39
    659 – 39 = 620 et comme d’habitude je teste 62 = 2 x 31, comme ça n’est pas un multiple de 13 je déduis que 659 n’est pas un multiple de 13.
  • Est-ce un multiple de 17 ?
    Pareil je sais que 7 x 7 = 49 donc je commence avec 17 x 7 = 119
    659 – 119 = 540 je teste 54 = 2 x 3³
    54 n’est pas multiple de 17 donc 540 n’est pas multiple de 17 et 659 n’est pas un multiple de 17.
  • Est-ce un multiple de 19 ?
    Là c’est cool, comme 19 se termine par 9, je fais directement 659 – 19 = 640
    Je teste 64 = 2^6, ça n’est pas un multiple de 19 donc 659 n’est pas un multiple de 19.
  • Est-ce un multiple de 23 ?
    Là je vais partir avec 23², je sais que 3² = 9 donc 23 au carré se termine par un 9.
    23² = 529 maintenant je fais 659 – 529 = 130
    13 n’est pas multiple de 23 donc 659 n’est pas multiple de 23.
  • Est-il premier ? Faut-il que je teste avec 29 ?
    Je sais que 30² = 900, logiquement 29² est entre 529 et 900 mais plus proche de 900
    Je suis un peu fainéante, je ne connais pas par cœur le carré de 29 et je me dis qu’il y en a peut-être un plus simple à calculer de tête. Par exemple 25².
    25² = 625 (je l’ai vraiment fait de tête, c’est simple il suffit de faire 500 + 125)
    Manque de chance pour moi 625 est inférieur à 659. Je pourrais essayer 26² mais je suis toujours aussi fainéante et je me dis qu’il sera plus simple de tester si 659 est multiple de 29 car les deux nombre se terminent par un 9. Et s’il n’est pas multiple de 29 alors je pourrais dire que 659 est premier.
    Je fais donc 659 – 29 = 630 je sais que 63 = 3² x 7 donc n’est pas un multiple de 29
    659 n’est pas un multiple de 29, inutile de tester s’il est multiple de 31 car 30² = 900.
    659 est donc un nombre premier.

Je vérifie avec mon petit tableau ou sur un moteur de recherche bien connu et je constate que 659 est bien un nombre premier, c’est la fête. Je vais tester un autre nombre de tête… mais en privé.
J’espère que ce petit article sur les nombres premiers vous aura intéressé. En tout cas c’est une passion bizarre que j’avais envie de partager même si elle ne va pas intéresser beaucoup de monde.

Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion /  Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s