Discussion :

[mo5bzn]

Un nombre est dit super premier s'il est premier et quand on supprime n'importe quel chiffre il reste premier. Exemple 113.
Voici un code source d'un programme qui permet d'afficher tous les super-premiers de 1 à n donné. J'attends vos avis :

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
program premier;
uses crt;
var n,i:longint;
 function prm(n:longint):boolean;
var i:longint;
begin
if n=1 then prm:=false else
   begin
   i:=2;
   while (n mod i <> 0) and (i<n) do i:=i+1;
   if i=n then prm:=true else prm:=false;
   end;
end;
 
function supprm(n:longint):boolean;
var ch,aux:string;
      m:longint;
      s,i:byte;
      e:integer;
begin
str(n,ch);
aux:=ch;
if prm(n)=false then supprm:=false else
   begin
   s:=0;
   for i:=1 to length(aux) do
      begin
      delete(ch,i,1);
      val(ch,m,e);
      ch:=aux;
      if prm(m)=true then s:=s+1;
      end;
   if s=length(aux) then supprm:=true else supprm:=false;
   end;
end;
 
begin
readln(n);
for i:=1 to n do
   begin
   if supprm(i)=true then writeln(i);
   end;
end.

[Roland Chastain]

Bonjour !

Le programme me paraît correct. J'ai juste une petite remarque, à propos de if prm(m)=true, qui pourrait s'écrire if prm(m). De même, if prm(n)=false pourrait s'écrire if not prm(n). En effet, le type boolean est fait pour représenter une proposition vraie ou fausse.

[droggo]

Lae,

Sans avoir testé, ça paraît correct.

Toutefois, la fonction prm est largement optimisable.

[DomDA91]

Dans le prolongement des remarques précédentes on peut aussi remplacer (ligne 11):

if i=n then prm:=true else prm:=false;

par

prm := (i=n);

et encore les parenthèses ne sont utile ici que pour une meilleure lisibilité.

[mo5bzn]

Merci beaucoup pour tous vos remarques. Ca fait vraiment plaisir

[anapurna]

Salut

Pour la recherche du nombre premier tu peux déjà limiter la recherche à la valeur entière de la racine carrée du nombre recherché.

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
 
  Function NombreFacteur(N:Integer):Integer;
  Var
    Count,I,Racine:Integer;
  Begin
    Count:=2;
    Racine:=Trunc(Sqrt(N));
    For I := 2 to Racine do
    Begin
      If N mod I = 0 Then
        Inc(Count);
    End;
    Result:=Count;
  End;
 
  Function Premier(N:Integer):Boolean;
  Begin
    Premier:=NombreFacteur(N) = 2;
  End;

Un autre un peu plus fin :

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
 
function prim ( n : integer ) : boolean ;
var
   i , lim : integer ;
   TestInt : boolean ;
begin
   if n<2 then
      TestInt:=false
   else 
   if n=2 then
      TestInt:=true
   else 
   if n mod 2 = 0 then
          TestInt:=false
   else
   begin
      i := 3;
      TestInt:=true ;
       lim:= trunc ( sqrt ( n ) ) ;
      while ( i<=lim ) and TestInt do
        if n mod i = 0 then 
          TestInt:=false
        else 
           i:=i+2
   end ;
   Result:=TestInt
end ;

[mo5bzn]

Pour la recherche du nombre premier tu peux déjà limiter la recherche à la valeur entière de la racine carrée du nombre recherché.

Une bonne idée de votre part, merci.
Je voudrais savoir si votre méthode va diminuer le temps de recherche des nombres premiers.

[pascalCH]

Une bonne idée de votre part, merci.
Je voudrais savoir si votre méthode va diminuer le temps de recherche des nombres premiers.

oui, limiter la recherche de diviseurs potentiels à la racine carrée du nombre réduit le nombre de boucles.
autre(s) technique(s) :

- tester "à la main" la parité (division par deux) et démarrer la boucle à partir de 3, faire des sauts de 2 en 2 (3,5,7....)

- un tout petit plus compliqué, appliquer une caractéristiques méconnue des nombres premiers, ils sont tous de la forme N = (6x +-1), avec 6x variant de 6 à racine de X + 1


@anapurna, la même avec une interruption de la boucle et étendue plus large :

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 IsPrimeFactor(N: UInt64): Boolean;
var
  Racine: UInt64;
  Loop:   UInt64;
begin
  if (N mod 2 = 0) or (N = 1) or (N = 2) then
    Result := False
  else
  begin
    Racine := Trunc(Sqrt(N)) + 1;
    Result := True;
    Loop := 3;
    while Loop < Racine do
    begin
      if N mod Loop = 0 then
      begin
        Result := False;
        break;
      end else
        Inc( Loop,2 );
    end;
  end;
end;

[droggo]

Kai,

Code :

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

1
2
3
4
5
6
7
8
9
function IsPrimeFactor(N: UInt64): Boolean;
var
  Racine: UInt64;
  Loop:   UInt64;
begin
  if (N mod 2 = 0) or (N = 1) or (N = 2) then
    Result := False
  else
...

Là, c'est carrément faux !

À force vouloir "simplifier", tu arrives à ce qui se produit souvent : erreur.

[pascalCH]

Kai,

Là, c'est carrément faux !

À force vouloir "simplifier", tu arrives à ce qui se produit souvent : erreur.

Oups !! effectivement, comme quoi, une ligne de plus ne fera pas de mal ...