Tester si un nombre est premier en Caml

Discutez d'informatique ici !
Stringer
Membre Naturel
Messages: 41
Enregistré le: 26 Mai 2010, 18:52

Tester si un nombre est premier en Caml

par Stringer » 28 Sep 2012, 19:22

Hello, voici j'ai un petit exo en cours de programmation fonctionnelle et je n'ai pas la moindre idée de comment le faire.

Il s'agit de tester si un nombre est premier ou non, par retour d'une phrase "vrai" ou "faux".

Sachant que je n'ai le droit qu'aux "if...else" et à la commande "match".

En revanche je peux supposer avec enregistré la fonction pgcd ...

Auriez vous une petite indication ? (juste une petite idée ! :lol3: )



Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 20:42

par Rockleader » 28 Sep 2012, 19:38

Ben, je connais pas le caml, mais l'algorithme me semble plus ou moins évident...


Entrer a
Entrer b
Si PGCD(a,b) = 1
Alors vrai
Sinon faux...


EN supposant que la fonction pgcd est déjà pré définies, sinon le vrai interêt du programme c'est plutot de construire cette fonction là.
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

Stringer
Membre Naturel
Messages: 41
Enregistré le: 26 Mai 2010, 18:52

par Stringer » 28 Sep 2012, 19:41

Il faut tester si un nombre est premier, pas si deux nombres sont premiers entre eux

faut pas abuser non plus :lol:

Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 20:42

par Rockleader » 28 Sep 2012, 19:56

Stringer a écrit:Il faut tester si un nombre est premier, pas si deux nombres sont premiers entre eux

faut pas abuser non plus :lol:



AH excuse moi, j'ai lu trop vite....

Bon, ben un nombre est premier s'il n'admet que pour seul diviseur naturel 1 et lui même il me semble.


Donc au final ça revient un peu au même.

Si tu fais le pgcd de a avec n'importe quel autre nombre différent de a lui même tu devrais trouver 1 et le nombre sera donc premier par définition.

A moins que je n'ai plus la bonne définition d'un nombre premier...
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 28 Sep 2012, 20:04

basiquement, tu programmes la division par (de 2 jusqu'à la racine carrée du nombre à tester) le nombre à tester. Si une division tombe juste, ton nombre n'est pas premier.

Stringer
Membre Naturel
Messages: 41
Enregistré le: 26 Mai 2010, 18:52

par Stringer » 28 Sep 2012, 20:08

nodjim a écrit:basiquement, tu programmes la division par (de 2 jusqu'à la racine carrée du nombre à tester) le nombre à tester. Si une division tombe juste, ton nombre n'est pas premier.


le problème n'est pas vraiment l'algorithme, mais plutôt la manière de coder.

En ADA ce serait assez simple avec l'utilisation des boucles, mais en Caml on a pas tout ça :mur:

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 28 Sep 2012, 20:26

Désolé je ne connais pas CAML.

Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 20:42

par Rockleader » 28 Sep 2012, 20:49

Stringer a écrit:le problème n'est pas vraiment l'algorithme, mais plutôt la manière de coder.

En ADA ce serait assez simple avec l'utilisation des boucles, mais en Caml on a pas tout ça :mur:


Il doit bien y avoir un moyen de faire une boucle...autrement si tu veux savoir si le nombre 999999997 est premier t'es dans la merde. C'est impossible de tester tous les cas seulement avec des if...
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 28 Sep 2012, 20:53

Il doit bien y avoir un moyen de faire une boucle

ou par récursion.
la vie est une fête :)

Stringer
Membre Naturel
Messages: 41
Enregistré le: 26 Mai 2010, 18:52

par Stringer » 28 Sep 2012, 22:22

fatal_error a écrit:ou par récursion.


Oui il faut utiliser de la récursion, mais je ne sais pas par quel bout prendre le programme :marteau:

C.Ret
Membre Relatif
Messages: 497
Enregistré le: 02 Juil 2012, 14:33

par C.Ret » 07 Oct 2012, 12:48

Désolé pour cette réponse tardive, qui de plus n'est peut-être pas très pertinante :

Je définierais la fonction Isprime(n) qui renvoi True si et seulement si n est premier en utilisant de façon récurrante une fonction interne IsDivisor(d,n) pour d= [2, 3, 4, ... sqrt(n) [

Au diable l'optimisation, je suis novice en chamaux :

Code: Tout sélectionner
LET  Isprime n =
    LET  REC  IsDivisor d n =
       IF d * d > n THEN True
       ELSE IF  MOD n d == 0 THEN False
       ELSE  IsDivisor (d+1) n
    IN IsDivisor 2 n ;;

 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 3 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite