Test de primalité récursif

Voir le sujet précédent Voir le sujet suivant Aller en bas

Test de primalité récursif

Message par Napoléon le Mer 28 Nov - 0:30

Qui pense que le programme suivant est évident?

Ecrire un programme récursif qui vérifie si un nombre N est premier ou non.
Un nombre est dit premier s'il n'est divisible que par 1 et par lui même.

scratch

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5312
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: Test de primalité récursif

Message par manianis le Mer 28 Nov - 11:04

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.

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 3695
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Re: Test de primalité récursif

Message par Napoléon le Mer 28 Nov - 11:38

manianis:
C'est une bonne solution.
Mais je crois qu'elle est un peu compliquée. On peut faire mieux au sens de la lisibilité.

De plus, si on offre à un utilisateur cette fonction récursive!, il aura du mal à comprendre pourquoi il y a 2 paramètres dans la fonction Est_Premier(X,Y) !

Logiquement, il doit avoir un seul paramètre Est_Premier(X).
Il y a des solutions biensûr, en est exemple la votre.

Mais, je crois que le test de primalité avec la récursivité est mauvais Smile

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5312
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: Test de primalité récursif

Message par manianis le Mer 28 Nov - 14:16

En effet, le sous-programme récursif devra savoir quels sont les nombres qu'il a testé commençant par 2 et jusqu'à sqrt(a) + 1( On peut démontrer facilement qu'il ne pourrait pas exister de diviseurs dans l'intervalle [sqrt(a), a div 2]) pour cette raison on utilise un deuxième paramètre qui indique le diviseur utilisé.

Je propose la solution suivante :

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;

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 3695
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Re: Test de primalité récursif

Message par suneddine le Mer 28 Nov - 23:28

un essai sans récursivité car c'est encore dur pour moi

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);}

}
avatar
suneddine
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 730
Age : 31
Localisation : tunisie
Réputation : 5
Points : 3762
Date d'inscription : 11/11/2007

Feuille de personnage
Capacité linguistique:
995/1000  (995/1000)

Revenir en haut Aller en bas

Re: Test de primalité récursif

Message par suneddine le Mer 28 Nov - 23:30

désolé, j'ai oublié <stdio.h> après #include au début du code
avatar
suneddine
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 730
Age : 31
Localisation : tunisie
Réputation : 5
Points : 3762
Date d'inscription : 11/11/2007

Feuille de personnage
Capacité linguistique:
995/1000  (995/1000)

Revenir en haut Aller en bas

Re: Test de primalité récursif

Message par Napoléon le Mer 28 Nov - 23:38

mosa:
regarde en haut: les commentaires de manianis.
Il n'est pas nécessaire d'aller jusqu'à a/2 ... !!!

ton programme doit fonctionner, mais il n'est pas très optimiséSmile

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5312
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: Test de primalité récursif

Message par methodiX le Jeu 29 Nov - 23:50

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!

_________________
Sami - Methodix, tunis
Le génie de Newton a consisté à dire que la lune tombe alors que tout le monde voit bien qu'elle ne tombe pas.
(Paul Valéry)
_____
Cliquer ici: Voir les nouveaux messages depuis votre dernière visite
Cliquer ici: Astuce: Utiliser l'outil "Recherche" du forum
avatar
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 4694
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: Test de primalité récursif

Message par manianis le Sam 1 Déc - 1:29

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!

J'ai lu/entendu/vu beaucoup de personnes parler de récursivité en disant tout problème résolvalble par l'itératif l'est en récursif et l'inverse est aussi correct, disaient-ils.

Certains privélégient l'itératif car il croient/pensent qu'il consomme moins de mémoire d'autres pensent que le récursif est plus intuitif on écrit la solution comme on y pense.

Moi je pense/croit/dit/vois que la programmation a pour but de resoudre des problèmes il faudra alors savoir utiliser l'outil adéquat lorsqu'il le faut.

Je cite un exemple (juste pour rigoler) pour planter un clou :
- on peut utiliser un marteau et tout va bien en quelques secondes
- on peut utiliser une pierre sous le prétexte que c'est gratuit et on découvre par la suite que cette pierre n'est pas assez dure pour planter un clou et on reste planté !!!
- on peut aussi utiliser une masse métallique de 20Kg. Là on risque de ne pas pouvoir la soulever, de plier le clou ou de casser la planche hôte du clou.

Conclusion : Je suis d'accord avec Methodix vérifier la primalité d'un nombre par la méthode récursive est simplement un exercice mental qui n'a aucun intérêt.

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 3695
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Re: Test de primalité récursif

Message par Napoléon le Sam 1 Déc - 1:35

D'habitude, il faut donner aux élèves des exercices où l'en sent la nécessité de la récursivité. Il y a tout un ensemble de règles pédagogiques qui doivent être respectées dans la création des exercices et des problèmes.

J'aime bien que quelqu'un qui possède un document sur la pédagogie le partage pour qu'on puisse le discuter ensemble.

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5312
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: Test de primalité récursif

Message par Napoléon le Mer 30 Sep - 0:22

Une autres solution (extraite d'un forum du Net):

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.

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5312
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: Test de primalité récursif

Message par faker62342 le Mer 4 Avr - 14:59

program ex;
uses wincrt;
var
n:integer;
t:boolean;
ch:char;
function premier (n:integer):boolean;
var
i,c:integer;
begin
i:=1;
c:=0;
while(i begin
i:=i+1;
if n mod i =0
then
c:=c+1;
end;
premier:=c=0;
end;
begin
repeat
clrscr;
readln(n);
t:=premier(n);
if t=true
then
writeln(n,' est premier')
else
writeln(n,' n''est pas premier');
repeat
writeln('DO YOU WANT TO REPEAT Y/N : ');
readln(ch);
until(upcase(ch)) in ['Y','N'];
until upcase(ch)='N';
write('FIN DUPROGRAMME');
end.

faker62342
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 1
Localisation : tunisie_monastir_sayada
Réputation : 0
Points : 2057
Date d'inscription : 04/04/2012

Revenir en haut Aller en bas

Re: Test de primalité récursif

Message par moudhafer salhi le Ven 27 Avr - 3:23

Sélectionner/Désélectionner multi-citation
Répondre en citant
Editer/Supprimer ce message
Supprimer ce message

Re: Test de primalité récursif

Message par moudhafer salhi Aujourd'hui à 1:38
Bonjour
La récursivité et l'optimisation de la récursivité a toujours posé un grand probleme.
Le grand avantage de la récursivité est la simplicité de codage(pas besoin de variable temporaire,ni compteur de boucle...etc)par contre son énorme probleme c'est la pile d'exécution qui peut s'exploser(pour cet exemple on est sure d'être à l'abris de ce probleme).
Alors le but est d'utiliser la force de la récursivité(simplicité de codage) et la contourner pour éviter le probleme de la pile,la solution est donc d'utiliser les fonctions récursives terminales(le terme terminale ça n'a rien à voir avec terminaison).
Une fonction récursive terminale c'est une fonction récursive dont l'appel de la fonction se fait aprés l'évaluation des paramètres et des variables.Ces fonctions sont évaluées exactement comme des fonctions itératifs,car on n'a pas besoin d'empiler l'appel de la fonction.
Prenons exemple pour mieux voir,je me permets d'ecrire en scheme car il est fait pour la récursivité c'est simple en plus:

Code:


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

regardons maintenant l'execution de (fact 3)=>on empile 3 et on passe a (fact 2)=>on empile 1 et on passe à (fact 1)=> on empile 1 et on passe à (fact 0)=> et là on scroll-back......
Optimosons là notre fonction en utilisant les fonctions recursives terminale:

Code:


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


En fait (tmp 1 3)=>(tmp 3 2)=>(tmp 6 1)=>(tmp 6 0)=>0,on voit bien quand on n'a rien empilé.




Revenons à notre exemple,pour le code de Manianis,je treouve que le test "d mod 2=0" n'est pas indispensable et l'eviter nous permet de gagner sqrt(N)/2 fois de test,voila ce que je propose

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

Merci

moudhafer salhi
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 7
Localisation : france
Réputation : 2
Points : 2102
Date d'inscription : 27/02/2012

Revenir en haut Aller en bas

Re: Test de primalité récursif

Message par Napoléon le Mer 2 Mai - 13:30

Merci Moudhafer !!!
Une très belle explication.

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5312
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: Test de primalité récursif

Message par moudhafer salhi le Ven 4 Mai - 2:29

De rien Smile

moudhafer salhi
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 7
Localisation : france
Réputation : 2
Points : 2102
Date d'inscription : 27/02/2012

Revenir en haut Aller en bas

Re: Test de primalité récursif

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut


 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum