Discussion :

[iks37]

Bonsoir à tous !

Je veux concevoir un programme permettant d'afficher les Nombres Premiers Jumeaux d'un intervalle donné.

Voici mon idée : détecter et compter les nombres premiers de l'intevalle, puis fixer la taille définitive d'un tableau dynamique. ensuite remplir ce tableau en parcourant à nouveau l'intervalle. enfin, en parcourant le tableau, afficher tous les couples de nombres vérifiant la condition (T[i] - T[i+1] = -2) : ces nombres sont en fait des Nombres Premiers Jumeaux.

Voici comment je la mets en oeuvre :

- le programme permet à l'utilisateur de fixer l'intervalle de recherche (donc par une saisie contrôlée)

- une fonction détecte d'abord les nombres premiers de l'intervalle, ensuite en détermine le nombre, et qu'il retourne au programme principal. ce nombre représentera la taille du tableau.

Le programme principal envoie en paramètres la borne inférieure, la borne supérieure (de l'intervalle) et la taille (donnée par le nombre de Nombres Premiers détectés), à une procédure.

- cette procédure est chargée de :
* déclarer un tableau dynamique dont elle fixe la taille ensuite
* remplir ce tableau des nombres premiers de l'intervalle
* afficher les nombres premiers jumeaux

Malheureusement, cette procédure ne "réagit" pas à son appel. Le compilation du programme dans son ensemble est sans erreur ni message.

Il y a certainenement une erreur de logique, mais Où ?

Voici la procédure :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
PROCEDURE premjum(borninf,bornsup,taille : integer);
          Var  i, j, d, code : integer; // d pour diviseur
               TabJum : array of integer;// déclaration d'un tableau dynamique
          Begin
               SetLength(TabJum, taille); // définition de la taille du tableau
               //remplissage du tableau
               for  i := 0 to (taille - 1)do
                   begin
                        for j := borninf to bornsup do
                            begin
                                 if(testprem(j)= 1)
                                 then (TabJum[i]):= testprem(j);
                            end;
                   end;
               //recherche et affichage des nombres premiers jumeaux
               for i:=0 to (taille-1) do
                   begin
                        if((TabJum[i] - TabJum[i+1]) = -2)
                        then write(' ','( ', TabJum[i], ' ; ', TabJum[i+1], ' )');
                   end;
               SetLength(TabJum, 0); // libération de la mémoire allouée
           End;

[Jipété]

Yep !

Y a un truc pas clair, là :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
for j := borninf to bornsup do
  if (testprem(j) = 1) then TabJum[i] := testprem(j);

Je suppose que testprem est une fonction pour tester si la valeur passée est première ou pas, OK ?
testprem retourne un boolean ou un integer ?
si boolean tu devrais avoir une erreur d'affectation à la compil sur TabJum[i] := testprem(j);
si integer, ben vu ton test, tu ne vas mettre que une fois 1 et encore, si borninf = 1 car sinon testprem(j) ne sera jamais égal à 1.
[EDIT] Cerveau embrumé hier soir -- voir mon post de dimanche matin [/EDIT]
si integer, tu remplis la case TabJum[i] avec 1 : c'est pas bon !

Enfin, il me semble...
Ou j'ai rien compris

[iks37]

Voici la fonction testprem :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
FUNCTION testprem(nombre : integer):integer;    // Fonction OK
         var i, d, code : integer;  // d pour diviseur
         begin
              for i := borninf to bornsup do
                  begin
                       d := 2;
                       while(((i MOD d)<>0)and(d<=sqrt(i)))do d := d + 1;
                       if((i MOD d)<>0)
                       then code := 1; // ce nombre est premier
                  end;
              testprem := code;
         end;

[Jipété]

Voici la fonction testprem :

qui renvoie bien un integer, comme je le supposais (Attention : je n'ai pas vérifié la validité mathématique de la fonction, pour ce point je te fais confiance).

Et donc tu remplis ton tableau avec des "1".

Enfin, il me semble...
Ou j'ai rien compris

[iks37]

Bon, je mets tout le programme que j'ai écrit :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
PROGRAM Compt_NombrPremiers_Jumeaux;
 
USES crt;
 
VAR aux : string;
    borninf, bornsup, taille : integer;
    TabJum : array of integer;  // déclaration d'un tableau dynamique
    rep : char;
 
FUNCTION fixborninf(aux : string): integer; //Saisir un naturel > 2
         Var auxconv, code : integer;
         Begin
           val(aux,auxconv,code);
           while((code <> 0)or((code = 0)and(auxconv <= 2)))do
                begin
                  writeln();
                  write('Saisie Invalide - Entrez un ENTIER NATUREL plus grand que 2 : ');
                  readln(aux);
                  val(aux,auxconv,code);
                end;
           if((code = 0)and(auxconv > 2))then fixborninf := auxconv;
         End;
 
FUNCTION fixbornsup(aux : string): integer; //Saisir un naturel > borne inférieure
         Var auxconv, code : integer;
         Begin
           val(aux,auxconv,code);
           while((code <> 0)or((code = 0)and(auxconv <= borninf)))do
                begin
                  writeln();
                  write('Saisie Invalide - Entrez un ENTIER NATUREL plus grand que ', borninf, ' : ');
                  readln(aux);
                  val(aux,auxconv,code);
                end;
           if((code = 0)and(auxconv > borninf))then fixbornsup := auxconv;
         End;
 
FUNCTION comptprem(borninf,bornsup : integer):integer;  // Fonction OK
         var i, d, compteur : integer;  // d pour diviseur
         begin
              compteur := 0;
              for i := borninf to bornsup do
                  begin
                       d := 2;
                       while(((i MOD d)<>0)and(d<=sqrt(i)))do d := d + 1;
                       if((i MOD d)<>0)
                       then compteur := compteur + 1; // ce nombre est premier
                  end;
              comptprem := compteur;
         end;
 
FUNCTION testprem(nombre : integer):integer;    // Fonction OK
         var i, d, code : integer;  // d pour diviseur
         begin
              for i := borninf to bornsup do
                  begin
                       d := 2;
                       while(((i MOD d)<>0)and(d<=sqrt(i)))do d := d + 1;
                       if((i MOD d)<>0)
                       then code := 1; // ce nombre est premier
                  end;
              testprem := code;
         end;
 
PROCEDURE premjum(borninf,bornsup,taille : integer);
          Var  i, j, d, code : integer; // d pour diviseur
               TabJum : array of integer;// déclaration d'un tableau dynamique
          Begin
               SetLength(TabJum, taille); // définition de la taille du tableau
               //remplissage du tableau
               for  i := 0 to (taille - 1)do
                   begin
                        for j := borninf to bornsup do
                            begin
                                 if(testprem(j)= 1)
                                 then (TabJum[i]):= testprem(j);
                            end;
                   end;
               //recherche et affichage des nombres premiers jumeaux
               for i:=0 to (taille-1) do
                   begin
                        if((TabJum[i] - TabJum[i+1]) = -2)
                        then write(' ','( ', TabJum[i], ' ; ', TabJum[i+1], ' )');
                   end;
               SetLength(TabJum, 0); // libération de la mémoire allouée
           End;
 
BEGIN
 Repeat
       clrscr;
       writeln();
       writeln('        ************************************************************');
       writeln('        * RECHERCHE DE NOMBRES PREMIERS JUMEAUX DANS UN INTERVALLE *');
       writeln('        ************************************************************');
       writeln();
       write(' Entrez la Borne Inferieure  : ');
       readln(aux);
       borninf := fixborninf(aux);
       writeln();
       writeln();
       write(' Entrez la Borne Superieure  : ');
       readln(aux);
       bornsup := fixbornsup(aux);
       taille := comptprem(borninf,bornsup);
       clrscr;
       writeln();
       writeln('        ************************************************************');
       writeln('        * RECHERCHE DE NOMBRES PREMIERS JUMEAUX DANS UN INTERVALLE *');
       writeln('        ************************************************************');
       writeln();
       writeln();
       writeln();
       writeln(' ***** Affichage du Resultat *****');
       writeln();
       writeln('  == Borne Inferieure  :  ', borninf);
       writeln();
       writeln('  == Borne Superieure  :  ', bornsup);
       writeln();
       writeln();
       write('  == Effectif de Nombres Premiers  : ', taille);
       writeln();
       writeln();
       writeln('  == Liste des Couples de Nombres Premiers Jumeaux entre ', borninf, ' et ', bornsup, ' :');
       writeln();
       writeln();
       //recherche et affichge des nombres premiers jumeaux
       premjum(borninf,bornsup,taille);
       writeln();
       writeln();
       write('Autre recherche (O/N) ? : ');
       readln(rep);
 Until(rep='N')or(rep='n');
END.

[Jipété]

Bon, je mets tout le programme que j'ai écrit :

Pour quoi faire, puisque tu as dit au début que le problème était dans la procédure premjum

J'aurais préféré que tu réfléchisses à la piste que j'ai indiquée : fais un test avec tes bornes à 1 et 5, en blindant ton code de "write" pour voir dans la console où il passe et où il ne passe pas en fonction des valeurs calculées.

Et sur ces bonnes paroles, au dodo ! (t'as vu l'heure ? )

[iks37]

Le programme n'admet que les entiers naturels strictement supérieurs à 2.
(Raisonnons avec ton exemple revu et corrigé).

Si on effectue un test avec les nombres 3 et 5, il affichera :

- effectif de nombres premiers : 2
- liste des couples de nombres premiers jumeaux entre 3 et 5 : <vide>

Commentaires

en effet, dans l'intervalle [3;5] d'entiers naturels, 3 et 5 sont des nombres premiers.
le programme crée alors un tableau de taille 2 qui devrait donc enregistrer les nombres 3 et 5.
de plus 3 - 5 = -2, alors les nombres 3 et 5 sont des nombres premiers jumeaux d'où l'affichage du couple
(3;5).

malheureusement, le programme n'affiche rien pour cette partie. or c'est la procédure qui s'en occupe. donc, je pense qu'elle ne réagit pas.

[Jipété]

Salut,

J'ai compris (et au passage, hier soir j'ai raconté une grosse bêtise, je vais éditer un post) :
ta fonction testprem qui renvoie un integer, tu devrais la renommer EstPremier et lui faire renvoyer un boolean, ça sera plus fluide pour le cerveau

Du coup ton test pourra s'écrire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if EstPremier(j) then TabJum[i] := j;

[iks37]

Bonsoir,

Il y a une "grosse erreur". En effet, c'est plutôt

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

then TabJum[i] := j;

au lieu de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

then TabJum[i] := testprem(j);

Mais la procédure reste toujours "muette"...

[Roland Chastain]

Bonsoir !

Il y a une boucle for de trop. Voici la correctionn que je suggère (sans l'avoir testée).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
//remplissage du tableau
//for  i := 0 to (taille - 1)do
//begin
i := 0;
for j := borninf to bornsup do
begin
  if testprem(j)= 1 then //TabJum[i]:= j;
  begin
    TabJum[i] := j;
    i := i + 1;
  end;
end;
//end;

[droggo]

Sia,

Désolé de mettre mon grain de sel, mais la fonction

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
FUNCTION testprem(nombre : integer):integer;    // Fonction OK
         var i, d, code : integer;  // d pour diviseur
         begin
              for i := borninf to bornsup do
                  begin
                       d := 2;
                       while(((i MOD d)<>0)and(d<=sqrt(i)))do d := d + 1;
                       if((i MOD d)<>0)
                       then code := 1; // ce nombre est premier
                  end;
              testprem := code;
         end;

ne teste pas du tout si son paramètre nombre est premier :
- quoi qu'il en soit par ailleurs, ce paramètre n'est jamais utilisé dans la fonction, et elle ne peut donc absolument rien en dire
- l'algorithme n'a pas grand chose à voir la détermination désirée
- et enfin, elle renvoie la valeur d'une variable locale qui n'a pas forcément été initialisée (elle ne l'est que par l'instruction
if((i MOD d)<>0) then code := 1; // ce nombre est premier
!!)

Pour programmer, une fonction X, en l'occurrence premjum, qui en utilise une autre Y, ici testprem, on commence par s'assurer du bon fonctionnement de Y.

[iks37]

En effet : la fonction testprem devrait plutôt recevoir borninf et bornsup en paramètres au lieu de nombre.

Ah, les inconvénients des "copier coller".

Je vais mettre de l'ordre dans ce désordre.

Bien vu monsieur Droggo, thanks !

[Roland Chastain]

En effet : la fonction testprem devrait plutôt recevoir borninf et bornsup en paramètres au lieu de nombre.

Mais à quoi servirait-elle, alors, cette fonction ? Cela n'est pas encore très clair.

Peut-être vaudrait-il mieux procéder par étapes, au lieu de chercher à tout faire d'un coup. D'abord, une fonction qui vérifie si un nombre est premier. Elle renverrait un résultat de type booléen. En voici une par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
program Premiers;
 
{$IFDEF VPASCAL}
  {&PMTYPE VIO}
  {&USE32+}
{$ELSE}
  {$APPTYPE CONSOLE}
  {$IFDEF FPC}{$MODE DELPHI}{$ENDIF}
{$ENDIF}
 
function EstPremier(const n: cardinal): boolean;
var
  d: cardinal;
begin
  if n < 2 then
    result := false
  else
    if n = 2 then
      result := true
    else
    begin
      d := 3;
      result := true;
      while (d < n) and result do
      begin
        if (n mod 2 = 0) or (n mod d = 0) then result := false;
        Inc(d, 2);
      end;
    end;    
end;
 
var
  i: cardinal;
 
begin
  for i := 0 to 99 do
    if EstPremier(i) then
      WriteLn(i);
 
  Write('Appuyez sur la touche Entr'#130'e... ');
  ReadLn;
end.

Une fois qu'on dispose de cette fonction, on peut s'intéresser à la recherche des jumeaux. Pour faire cette recherche, on pourrait procéder beaucoup plus simplement que vous ne l'avez fait. Voici un programme qui cherche les nombres premiers et jumeaux de 1 à 100000 et les enregistre dans un fichier texte. J'ai mis un chronomètre : sur ma machine il faut à peu près neuf secondes pour faire le travail. Qui dit mieux ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
program Jumeaux;
 
{$IFDEF VPASCAL}
  {&PMTYPE VIO}
  {&USE32+}
{$ELSE}
  {$APPTYPE CONSOLE}
  {$IFDEF FPC}{$MODE DELPHI}{$ENDIF}
{$ENDIF}
 
{$B-}
 
uses
  Windows,  // GetTickCount
  SysUtils; // IntToStr
 
function EstPremier(const n: cardinal): boolean;
var
  d: cardinal;
begin
  if n < 2 then
    result := false
  else
    if n = 2 then
      result := true
    else
    begin
      d := 3;
      result := true;
      while (d < n) and result do
      begin
        if (n mod 2 = 0) or (n mod d = 0) then result := false;
        Inc(d, 2);
      end;
    end;    
end;
 
function EstJumeau(const n: cardinal): boolean;
begin
  result := EstPremier(n) and (EstPremier(n - 2) or EstPremier(n + 2));
end;
 
var
  i: cardinal;
  a, b: cardinal;
  t: text;
begin
  Assign(t, 'Jumeaux.txt');
  Rewrite(t);
 
  a := GetTickCount;
 
  i := 1;
  while i <= 1E5 do
  begin
    if EstJumeau(i) then
      WriteLn(t, i);
    Inc(i, 2);
  end;
 
  b := GetTickCount;
 
  Close(t);
 
  WriteLn('Temps '#130'coul'#130' : ', IntToStr(b - a), ' millisecondes.');
  Write('Appuyez sur la touche Entr'#130'e... ');
  ReadLn;
end.

[Jipété]

Salut Roland,

(...) Voici un programme qui cherche les nombres premiers et jumeaux de 1 à 100000 et les enregistre dans un fichier texte.

Hey, pas mal du tout

(...) J'ai mis un chronomètre : sur ma machine il faut à peu près neuf secondes pour faire le travail. Qui dit mieux ?

Moi !
973 millisecondes sur ma machine Debian Wheezy 32 bits. 10 fois moins, lol !

[Roland Chastain]

Bonjour Jipété ! Merci pour le retour.

973 millisecondes sur ma machine Debian Wheezy 32 bits. 10 fois moins, lol !

Je ramène immédiatement mon ordinateur au magasin.

Autrement, quelle que soit la machine, ça devrait aller encore plus vite comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function EstPremier(const n: cardinal): boolean;
var
  d: cardinal;
begin
  if n < 2 then
    result := false
  else
    if n = 2 then
      result := true
    else
      if n mod 2 = 0 then
        result := false
      else
      begin
        d := 3;
        result := true;
        while (d < n) and result do
        begin
          if n mod d = 0 then result := false;
          Inc(d, 2);
        end;
      end;    
end;

[Jipété]

Autrement, quelle que soit la machine, ça devrait aller encore plus vite comme ça :

Perdu
Entre 1009 msec (1st run) et 999 msec (2nd run)

La suite ce soir...

[Roland Chastain]

Perdu

C'est curieux. Chez moi la deuxième version s'exécute en 4 secondes environ, contre 9 secondes pour la précédente.

[Jipété]

Yop !

Et v'là même une autre version, les précédentes n'incluant pas "1" dans le fichier.

Maintenant, "1" est-il un nombre premier ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function EstPremier(const n: cardinal): boolean; 
var
  d: cardinal;
begin
  result := false;
  if n = 2 then
    result := true
  else
    if n mod 2 = 0 then
      result := false
    else
    begin
      d := 3;
      result := true;
      while (d < n) and result do
      begin
        if n mod d = 0 then result := false;
        Inc(d, 2);
      end;
    end;
end;

En termes de perf's, c'est kif-kif, je tourne selon les versions, les phases de la Lune et l'heure qu'il est, entre 99x et 100x msec.

[Roland Chastain]

Maintenant, "1" est-il un nombre premier ?

Les savants disent que le nombre un n'est pas premier, parce ses deux diviseurs ne sont pas distincts. Mais comme il est certain que ce n'est pas un nombre composé, le commun des mortels a du mal à croire les savants sur ce point.

[droggo]

Jia,

Maintenant, "1" est-il un nombre premier ?

Les savants disent que le nombre un n'est pas premier, parce ses deux diviseurs ne sont pas distincts. Mais comme il est certain que ce n'est pas un nombre composé, le commun des mortels a du mal à croire les savants sur ce point.

J'ai déjà donné la réponse, voir (entre autres)

http://www.developpez.net/forums/d13...n-premier-non/