Test de primalité récursif

Code:

program Primalite;

function Est_Premier(a, d : integer):boolean;
begin
    (* si aucun diviseur trouvé jusqu'à sqrt(a) + 1 alors a est premier *)
    if (d > (sqrt(a) + 1)) then Est_Premier := True
    else if (a mod d = 0) then Est_Premier := False
    else begin
        (* On essaye uniquement avec les nombres impairs *)
        if (d mod 2 = 0) then d := d - 1;
       
        Est_Premier := Est_Premier(a, d + 2);
    end;
end;

var i, a : integer;
begin
    Readln(a);
    for i:=2 to a do begin
        if (Est_Premier(i, 2)) then
          Writeln(i, ' est premier')
        else
          Writeln(i, ' n''est pas premier');
    end;
     
    Readln;
end.


Code:

function Chercher_Div(a, bi, bs : integer):boolean;
begin
    if (bi > bs) then Chercher_Div := False
    else if (a mod bi = 0) then Chercher_div := True
    else begin
        Chercher_Div := Chercher_Div(a, bi + 2, bs);
    end;
end;

function Est_Premier(a : integer):boolean;
begin
    if (a > 2) and (a mod 2 = 0) then Est_Premier := False
    else Est_Premier := not Chercher_Div(a, 3, trunc(sqrt(a) + 1));
end;

Code:


# include

int main()
{int a, i=2;
bool ent_prem = true;

printf(" saisir un entier ");
scanf("%d",&a);

do
{if (a % i != 0)
{ent_prem = true;
 i++;}
else {ent_prem=false;}}
while ((ent_prem = true) && (i<=a/2));

if (ent_prem == true)
{printf("%d est un entier premier",a);}
else
{printf("%d n'est pas un entier premier",a);}

}


methodiX a écrit:La récursivité et les nombres premiers. C'est un exercice embettant, je l'ai trouvé quelque part dans une photocopieuse à tunis. Il parait que ça vient d'un Devoir de Contrôle Tunisien.

A mon avis, il a une difficulté très artificielle!

Code:

program Exercice_15 ;
uses wincrt ;
var
n:integer ;

{ ============ CORPS DE LA PROCEDURE SAISIR ===================}

procedure saisir (var n:integer);
begin
writeln('donner un entier');
readln(n);
End;

{ ============ CORPS DE LA FONCTION PREMIER ===================}

function premier(n,d,p:integer):boolean;
begin
if (n=1) and (p=0) then
premier:=true
else if (p=0) and (d>1) then
if n mod d=0 then
begin
p:=p+1;
premier:=false
End
else premier:=premier(n,d-1,p);
End;

{ ============ CORPS DE PROGRAMME PRINCIPAL ===============}

begin
saisir(n);
if premier(n,(n div 2),0) then
writeln(n,' est un nombre premier')
else
writeln(n,' n''est pas un nombre premier');
End.

Code:



    (define (fact n)
        (if (= n 0)
            1
            (n*fact(n-1))
        )
    )



Code:



    (define (factbis n)
      (define (tmp x y)
          (if (= y 0)
              x
              (tmp (* x y) (- y 1))
          )
      (tmp 1 n)
    )



Code:


function est_premier(var n;integer,d:integer):boolean;
begin
if(d>sqrt(n)) est_premier:=true
//pas besoin de faire des else le return arrete la fonction(c'est juste moins long et ça nous evite de verifier de end(des crochets en autre langages))
if(n%d)==0 then est_premier=false
est_premier:=est_premier(n,d+2)//pas la peine de tester la parité de d car on est sure que d et d+2 sont impaires(intialisation de d est 3
end;

function est_premierPrincip(var n:integer):boolean
if(n=2) then est_premierPrincip:=false//ou true j'ai oublié si 2 est paire ou non ,quelle honte $
est_premierPrincip=est_premier(n,3)
end