NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 27/01/2017

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

Nombres PREMIERS

 

Débutants

Nombres

Premiers

ORDRE géométrique

 

Glossaire

Nombres

Premiers

 

 

INDEX

 

Nombres premiers – ORDRE

 

Crible d'Ératosthène

Programmation

Crible de Sundaram

Tableaux

Cercles et croix

Spirales d'Ulam

Conjecture de Gilbreath

Carrés magiques premiers

Méthode René Nève

 

Sommaire de cette page

>>> Crible

>>> Limite d'exploration

>>> Algorithme

>>> Programmation

>>> Application: nombres premiers d'Euler

 

 

 

 

 

 

Crible d'Ératosthène

Programmation

  

*      Exemple d'initiation à la programmation.

*      Voir bases sur le crible d'Ératosthène..

 

Ératosthène de Cyrène

(276 - 194 av. J.-C. )

Eratosthenes of Cyrene

(276-194 BC)

Anglais: The Sieve of Eratosthenes

 

 

 

Liminaire –

Pour déterminer si p est premier

 

*    Les logiciels évolués donnent la réponse à l'aide d'une instruction

du type "premier(p)" ou "isprime(p)" … selon le logiciel considéré.

 

*    Mais, sans cette instruction magique, il faut revenir à la bonne vielle méthode du crible d'Ératosthène

*    C'est à dire: chercher si p est divisible par successivement

l'un des nombres de 2 à p.

*    En fait, on sait que l'on peut limiter la recherche aux nombres

à la racine de p.

 

 

 

RAPPEL: fonctionnement du crible

 

*    On écrit tous les nombres.

*    On élimine tous ceux qui sont divisibles par 2, puis par 3.

*    Ainsi de suite pour tous les nombres les plus petits qui restent.

 

Ces nombres successifs qui restent sont des nombres premiers.

 

 

Élimination des nombres pairs

 

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

Élimination des nombres divisibles par 3

 

 

2

3

5

7

9

11

13

15

17

19

21

23

25

27

29

31

33

35

37

39

41

43

45

47

49

51

53

55

57

59

61

63

65

67

69

71

73

75

77

79

81

83

85

87

89

91

93

95

97

99

101

103

105

107

109

Élimination des nombres divisibles par 5

 

2

3

5

7

 

11

13

 

17

19

 

23

25

 

29

31

 

35

37

 

41

43

 

47

49

 

53

55

 

59

61

 

65

67

 

71

73

 

77

79

 

83

85

 

89

91

 

95

97

 

101

103

 

107

109

Ensuite, avec 7

 

*    Tous les nombres non en jaune sont premiers.

*    Il y en a 25 jusqu'à 100.

*    Les quatre nombres premiers de tête sont particuliers: séparés par une ou deux unités.

*    Notez que le 1 n'est pas premier.

2

3

5

 

 

 

7

 

11

13

17

19

 

23

 

29

31

 

37

 

41

43

47

49

 

53

 

59

61

 

67

 

71

73

77

79

 

83

 

89

91

 

97

 

101

103

107

109

Voir Méthode de la barre magique

 

 

 

LIMITE D'EXPLORATION

 

*    Il est inutile de prolonger les recherches au-delà de racine de n.

 

Exemple avec n = 100:

*    On cherche un produit dont les deux facteurs se rapprochent de l'égalité, pour se rapprocher de la configuration de la racine carrée.

*    On commence par une grande fourchette que l'on rétrécit progressivement.

 

2

4

5

 

10

20

25

 

50

 

 

 

 

 

 

 

 

 

 

 

 

2x 50 = 100

 

 

 

 

 

 

 

 

 

 

4 x 25 = 100

 

 

 

 

 

 

 

 

 

 

5 x 20 = 100

 

 

 

 

 

 

 

 

 

 

10 x 10 = 100

 

*    Pour chercher la divisibilité de 100.

*    On explore les nombres successifs: 2, 3, 4, …

*    Lorsqu'on dépasse 10, le quotient est inférieur à 10.

*    On retrouve les nombres déjà explorés.

*    Sorte de symétrie.

 

Conclusion: pour rechercher la racine de 100, on peut se contenter de n'explorer que jusqu'à 10, nombre qui est la racine de 100.

 

 

 

ALGORITHME - Phasage

 

*    Trois phases pour programmer le crible:

*    Dessin de l'organigramme;

*    Programmation des instructions; et

*    Écriture dans le langage de programmation.

 

 

 

ALGORITHME - Organigramme

 

Pour un nombre p, candidat pour être premier, nous explorons toutes les valeurs d'un nombre i depuis 2 jusqu'à racine de n.

Pour chaque valeur de i nous cherchons s'il est un diviseur de n. Si oui, c'est que le nombre est composé. Nous mémorisons ce fait et nous poursuivons (bêtement) l'exploration pour ne pas compliquer l'algorithme (pour le moment).

Le nombre est décrété premier si aucun diviseur n'a été trouvé.

 

Voir Algorithme

 

ALGORITHME – Programmation

 

Programme

Commentaires

On se donne p

Donnée d'entrée dans ce programme de test de primalité de p.

 

 

 

 

 

Initialisation de la boucle de test.

 

imax := racine de p

Valeur maximale pour le crible.

 

premier:=1

 

 

On fait l'hypothèse que p est premier

On place un indicateur dans cette position par défaut et on va observer s'il résiste dans cette position.

 

 

 

 

 

Lancement de la boucle de test.

 

Boucle pour i à partir de 2

jusqu'à imax

Il s'agit d'une boucle d'itérations.

Le programme effectue le parcours de la boucle pour toutes les valeurs de i.

 

 

Division de p par i

Division par toutes les valeurs successives que prend i.

 

 

Quotient entier ?

Si le quotient est entier, c'est que p est divisible par i.

 

 

 

Oui

premier :=0

p est divisible par i, p est composé, p n'est pas premier.

 

 

 

Non

aucune action

On conserve l'indicateur premier dans son état.

 

 

Fin de la boucle

L'exploration pour chacun des nombres

de 2 à i max est finie.

 

 

 

 

Fin de la boucle de test.

premier à 1 si p est premier

premier à 0 si p est composé

On observe l'indicateur "premier"

Dans la suite du programme,

il suffit de tester la valeur de l'indicateur

pour savoir si p est premier ou non.

 

Une première amélioration consiste à stopper l'exploration dès que le nombre est détecté comme composé. Facile, il suffit de forcer i à prendre tout de suite la valeur de la racine de n.


On peut bien évidemment améliorer l'algorithme en n'explorant que les nombres impairs et même mieux, que les nombres premiers déjà trouvés (mais alors, il faut les avoir mémorisés au fur et à mesure).

On peut encore limiter le nombre des recherches en explorant uniquement les nombres en 6n plus ou moins un, car tous les nombre premiers sont de cette forme.

 

Voir Programmation

 

 

ALGORITHME – Écriture du programme

 

p:=109:

   imax:=round(sqrt(p)):

   premier:=1:

 

  

for i from 2 to imax do

 

 

        div:= evalf(p/i):

      

       if frac(div)=0 then

          

                 premier:=0:

       fi: 

  

  od:

 

     

      if premier=1 then

          lprint(p, est_premier):

    fi:

 

On prend p = 109 comme exemple.

 

Sa racine arrondie est placée en imax, qui doit être un nombre entier.

On positionne l'indicateur premier à 1.

 

On lance la boucle d'exploration. Dont l'anglais se lit en français:

"pour i de 2 à imax faire"

 

Le résultat de la division évalué en décimal est placé en div.

 

Si la partie décimale est nulle, le nombre est entier.

Et, p est divisible par un i; l'indicateur premier est mis à 0.

Fin du test de divisibilité.

 

Fin de la boucle d'exploration en i.

 

 

Si l'indicateur premier est à 1, le nombre est premier.

L'imprimer.

Fin.

109  est_premier

<=  Exécution du programme.

Programmation du type Mapple (marque Waterloo Mapple, logiciel mathématique)

 

 

APPLICATION –

Premiers d'Euler en n² + n + 41

 

k:=0:

 

 for n from 1 to 107 do

  

       p:= n*n + n + 41:

 

 

On initialise un compteur k pour comptabiliser la quantité de premiers trouvés.

Boucle sur la plage de recherche.

Ici;: tous les nombres n de 1 à 107

Calcul du nombre p à partir de la valeur de n.

   imax:=round(sqrt(p)):

   premier:=1:

 

   for i from 2 to imax do

        div:= evalf(p/i):

        if frac(div)=0 then

           premier:=0:

       fi: 

   od:

 

   if premier=1 then

          lprint(k, n, p):

   fi:

Programme de recherche si p est premier

C'est exactement celui vu ci-dessus.

 

 

Lors de l'impression si p est premier,

on donne aussi la valeur de n correspondante et  la quantité de premiers déjà trouvé.

 od:

 

lprint ( evalf ( 100*k / (n-1) ) ) ;

Fin de la boucle d'exploration en n.

 

On imprime le pourcentage

de nombres premiers trouvés

par rapport à la quantité de nombres explorée.

Voir Nombres premiers d'Euler

 

Résultat de l'exécution

 

On trouve successivement k, numéro; n, la variable; et, p le nombre premier d'Euler associé à n.

 

1   1    43

2   2    47

3   3    53

4   4    61

5   5    71

6   6    83

7   7    97

8   8   113

9   9   131

10   10   151

11   11   173

12   12   197

13   13   223

14   14   251

15   15   281

16   16   313

17   17   347

18   18   383

19   19   421

20   20   461

21   21   503

22   22   547

23   23   593

24   24   641

25   25   691

 

26   26   743

27   27   797

28   28   853

29   29   911

30   30   971

31   31   1033

32   32   1097

33   33   1163

34   34   1231

35   35   1301

36   36   1373

37   37   1447

38   38   1523

39   39   1601

40   42   1847

41   43   1933

42   45   2111

43   46   2203

44   47   2297

45   48   2393

46   50   2591

47   51   2693

48   52   2797

49   53   2903

50   54   3011

 

51   55   3121

52   57   3347

53   58   3463

54   59   3581

55   60   3701

56   61   3823

57   62   3947

58   63   4073

59   64   4201

60   66   4463

61   67   4597

62   68   4733

63   69   4871

64   70   5011

65   71   5153

66   72   5297

67   73   5443

68   74   5591

69   75   5741

70   77   6047

71   78   6203

72   79   6361

73   80   6521

74   83   7013

75   85   7351

 

76   86   7523

77   88   7873

78   90   8231

79   92   8597

80   93   8783

81   94   8971

82   95   9161

83   97   9547

84   98   9743

85   99   9941

86   100   10141

87   101   10343

88   103   10753

89   105   11171

90   106   11383

91   107   11597

 

 

 

 

 

 

85,0467

 

Sur cette plage pour n jusqu'à 107, la proportion de nombres premiers d'Euler est de 85%.

 

 

 

 

Bilan et suite moderne

La recherche des nombres premier en utilisant le crible d'Ératosthène  est vite limité du fait de sa gourmandise en place mémoire.

En 2016, Harald Helfgott développe un algorithme qui réduit le besoin de place par 100 ou plus. C'est lui qui, en 2013, a démontré la conjecture faible de Goldbach (tout nombre plus grand que 5 est la somme de trois nombres premiers).

 

Mais Helfgott s’est inspiré d’une technique de calcul analytique appelé la méthode du cercle pour que le crible d’Ératosthène fonctionne avec peu de mémoire. En termes mathématiques, plutôt que d’utiliser un espace N, le crible utilise la racine cubique de N. Selon Helfgott, pour calculer tous les nombres premiers jusqu’au trillion, la version modifiée du crible nécessite quelques millions de bits au lieu de milliards de bits.

 

Source: New Take on an Ancient Method Improves Way to Find Prime Numbers

The modified version of the sieve of Eratosthenes could accelerate computer calculationsScientific American et sa tradition en: Mathématiques – Le Crible d’Ératosthène pour optimiser la recherche des nombres premiers – Jacqueline Charpentier – 28/09/2016  (Actualité Houssenia Writnig).

 

 

 

 

 

Voir

*    Crible de Sundaram

*    Crible d' Ératosthène

*    Nombres premiersIndex

Aussi

*    Liste de nombres premiers

 

*    Nombres composés

*    Représentation des nombres

*    Facteurs premiers autour de 1000

*    ProgrammationIndex

*    Premiers en tableaux, en spirales …

*    Ératosthène

Sites

*    Crible - applet amusante

*    A User's Guide to the Sieve of Eratosthenes Applet

Programmation

*    Programmation en JAVASCRIPT par Serge Mehl

*    The Sieve of Eratosthene - programming the sieve C++ and other

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Premier/eratoprg.htm