Tester si un nombre est premier en Caml
Discutez d'informatique ici !
-
Stringer
- Membre Naturel
- Messages: 41
- Enregistré le: 26 Mai 2010, 18:52
-
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: )
-
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:
-
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
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.
-
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 !
-
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 ;;
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 3 invités