Lisp - nombre premier

Je suis en train d'apprendre lisp et j'ai quelques difficultés avec les nombres premiers. J'ai besoin d'une fonction is-prime et si c'est le premier que j'ai pour revenir t et si elle n'est pas-je retourner nil.

(prime 41) => t

(prime 35) => nil

Pour l'instant j'ai:

(defun is-prime (n d) 
  (if (= d 1) 
      (print "t") 
      (if (= (% n d) 0) 
          (print "nil") 
          (is-prime (n (- d 1) )))))

mais j'ai 2 paramètres, et je n'ai aucune idée de comment l'utiliser seul. De Plus, il ne fonctionne pas à tous. Quelqu'un peut-il m'aider? Merci!

OriginalL'auteur mad scientist | 2013-12-15

  1. 5

    vous avez quelques faux pas là:

    (defun is-prime (n d) 
  (if (= d 1) 
      (print "t") 
      (if (= (% n d) 0) 
          (print "nil")

    Tout d'abord, ne pas print vos résultats, il suffit de les retourner. Deuxièmement, il n'y a pas % fonction, c'est rem.

    La véritable erreur est de savoir comment vous faites l'appel récursif. Vous avez un supplément de parenthèses:

              (is-prime (n (- d 1) )))))
          ;         ^          ^

    en Lisp, les parenthèses signifient un appel de fonction; mais vous n'avez pas l'intention d'appeler n avec un argument (- d 1), ils sont tous les deux des arguments à is-prime. Donc nous avons juste besoin de le changer à

              (is-prime  n (- d 1)  ))))

    Alors que faut-il faire? Il compte: d, (- d 1) ... 1. Et quand (= d 1), il retourne t. Donc, d'une façon d'appeler, il est

    (defun is-prime (n &optional (d (- n 1))) 
  (or (= d 1)
      (and (/= (rem n d) 0)
           (is-prime  n (- d 1)))))

    mais il n'est pas le moyen le plus efficace, :), ni le plus fort, soit. Il est beaucoup mieux pour compter vers le haut, pas vers le bas pour une chose, parce que tout nombre est beaucoup plus susceptibles d'avoir un petit facteur de la plus grande. Ensuite, il nous permet d'optimiser où nous arrêter.

    Cela semble lisse. Pouvez-vous commenter la récursivité et la transmission de paramètres? Ne l'appel de la fonction elle-même en passant par la suite la diminution de la deuxième paramètre à chaque fois?
    l'appel de la fonction elle-même en passant par la suite la diminution de la deuxième paramètre à chaque fois?" oui. Pas tout le temps, si elle a besoin de le faire -- c'est à dire si d n'était pas 1 (quand T est retourné), et (rem n d) n'était pas 0 (quand NIL est retourné).
    Je vois. Il semble que la fonction des pauses lorsqu'elle est appelée avec l'argument 1. Il donne de la division par zéro.
    la droite. 🙂 c'est ce que j'allusion, avec "pas ... le plus sûr [moyen d'appeler cette fonction]". 🙂
    L'a obtenu. De sorte que certains de la vérification dans l'ordre dans le début? Aussi, il est possible d'optimiser par la seule vérification d = isqrt(n) et ci-dessous.

    OriginalL'auteur Will Ness

  2. 1

    J'ai prises Ness réponse comme une source d'inspiration et modifié la fonction. Voici le code. Est vérifie si 1 est transmise en tant que paramètre et permet de s'assurer de sortie nil devrait être le cas. 

    (defun is-prime (n &optional (d (- n 1))) 
  (if (/= n 1) (or (= d 1)
      (and (/= (rem n d) 0)
           (is-prime  n (- d 1)))) ()))

    Je suis toujours en apprentissage Common Lisp, donc si il y a des problèmes avec cela, s'il vous plaît laissez-moi savoir.

    il est beaucoup mieux compter de 2 à sqrt(n) (inclus), au lieu de compter à partir de (n-1) 2. aussi, Common Lisp n'aime pas la récursivité; votre intention est une boucle afin de mieux l'écrire comme une boucle. Avec loop, ou do, ou prog même. comme pour votre code, vous n'êtes toujours pas gérer les cas où (< n 1).

    OriginalL'auteur MadPhysicist

  3. 0

    Bien, vous êtes à mi-chemin.

    Voici mon explication en anglais:

    Que vous avez écrit en lisp une fonction est-prime (btw, "oui ou non", comme les fonctions qui sont habituellement nommé, quelle que soit la p en lisp) qui vous dit que si n est relativement premier à d.

    Ce que vous devez faire est d'aller à travers tous les d est inférieur à n, et si c'est pas relativement premier avec l'un d'eux, de retour néant, mais si, après que la boucle que vous n'avez pas retourné néant, puis retour t. Votre ami ici est la fonction "mod", qui vous dit si il y a un reste lors de son premier argument est divisée par la seconde.

    Quelque chose comme:

    (defun primep (n)
 (cond
  ((= 1    n)          nil)
   (t
   (loop
     :with root     = (isqrt n)
     :with divisors = (loop :for i :from 3 :to root :by 2 :collect i)
     :for d = (pop divisors)
     :if (zerop (mod n d))
     :do (return nil)
     :else :do (setf divisors (delete-if (lambda (x) (zerop (mod x d))) divisors))
     :while divisors
     :finally (return t)))))

    Aussi, n'imprimez pas nul, juste retour néant.

    Je vois ce que tu fais ici, mais j'essayais de faire récursive. Comment puis-je faire en récursif et ne conserver qu'un seul paramètre n ?
    Peut-être, mais ce n'est pas un candidat pour la queue de la récursivité, donc il n'y a pas une bonne raison pour le faire récursive (Lisp est beaucoup plus que des fonctions récursives...). Laissez-moi voir ce que je peut faire ensemble...

    OriginalL'auteur Bandrami