Напечатайте первые N простых чисел в Common Lisp

Я делаю функцию Common Lisp для печати первых N простых чисел. Пока мне удалось написать этот код:

;globals 
(setf isprime 1) ;if 1 then its a prime, 0 if not.
(setf from 1)    ;start from 1
(setf count 0)   ;should act as counter to check if we have already 
                 ;    N primes printed

;function so far.
(defun prime-numbers (to)
  (if (> count to) nil(progn
      (is-prime from from)
      (if (= isprime 1) (print from)(setf count (+ count 1)))
      (setf isprime 1)
      (setf from (+ from 1))
      (prime-numbers to)))
  (if (>= count to)(setf count 0) (setf from 1)))  

;code to check if a number is prime    
(defun is-prime(num val)
  (if (< num 3) nil 
    (progn
      (if (= (mod val (- num 1)) 0) (setf isprime 0))
      (is-prime (- num 1) val))))

Моя проблема в том, что он неправильно печатает N простых чисел. Если я вызову >(prime-numbers 10), результаты будут: 1 2 3 5 7 11 13 17 19 1, т. е. он правильно напечатал только 9 простых чисел.

но тогда, если я позвоню >(prime-numbers 2), результаты будут: 1 2 3 5 7 1

что я тут не так делаю?? это мой первый опыт написания кода на LISP.

ОБНОВИТЬ:

  (defparameter from 1)
  (defparameter count 0)

  (defun prime-numbers (to)
     (if (> count to)nil
         (progn
            (when (is-prime from) 
                (print from)
                (setf count (+ count 1)))
            (setf from (+ from 1))
            (prime-numbers to)))
     (when (>= count to)
         (setf count 0) 
         (setf from 1)))  

  (defun is-prime (n)
    (cond ((= 2 n) t)
     ((= 3 n) t)
     ((evenp n) nil)
     (t 
       (loop for i from 3 to (isqrt n) by 2
             never (zerop (mod n i))))))

работает отлично. но в конце выводит NIL.


numbers printing lisp primes clisp
person binaryjc    schedule 04.04.2013    source источник
comment
Пожалуйста, исправьте форматирование кода и удалите обратные кавычки перед defuns   -  person sds    schedule 04.04.2013
comment
CLISP — это реализация языка программирования Common Lisp.   -  person Rainer Joswig    schedule 04.04.2013
comment
Я изменил ваш первый код и не трогал второй. У вас там какой-то неправильный отступ.   -  person Will Ness    schedule 04.04.2013

Ответы (2)


arrow_upward
7
arrow_downward

Во-первых, здесь вообще нет необходимости использовать глобальные переменные.

Используйте возвращаемые значения true/false. Это позволит вашей функции is-prime выглядеть примерно так:

(defun is-prime (n)
  (cond ((= 2 n) t) ;; Hard-code "2 is a prime"
        ((= 3 n) t) ;; Hard-code "3 is a prime"
        ((evenp n) nil) ;; If we're looking at an even now, it's not a prime
        (t ;; If it is divisible by an odd number below its square root, it's not prime
           (loop for i from 3 to (isqrt n) by 2
                 never (zerop (mod n i))))))

Таким образом, функция не полагается ни на какое внешнее состояние, и нет ничего, что могло бы что-то спутать.

Во-вторых, последнее 1, которое вы видите, является (вероятно) возвращаемым значением функции.

Чтобы проверить это, попробуйте: (progn (prime-numbers 10) nil)

В-третьих, перепишите свою функцию prime-numbers, чтобы она не использовала глобальные переменные.

В-четвертых, никогда не создавайте глобальные переменные с setf или setq используйте либо defvar или defparameter. Также (в основном, но некоторые не согласны) хороший стиль использовать *earmuffs* для ваших глобальных (действительно, «специальных») переменных.

person Vatine    schedule 04.04.2013
comment
вы можете использовать always в своем loop вместо return-from. - person sds; 04.04.2013
comment
@sds Верно. Прошло несколько лет с тех пор, как я писал циклы в гневе, и return-from было в пределах досягаемости. - person Vatine; 04.04.2013
comment
@sds Переписано с использованием never. - person Vatine; 04.04.2013
comment
Спасибо тебе за это!. но у меня все еще нет необходимых выходов. кроме глобалов. что может быть не так с моими простыми числами? - person binaryjc; 04.04.2013
comment
@binaryjc Я действительно думаю, что использование глобальных переменных вызывает вашу проблему. Использование глобального состояния для связи между функциями — это почти лучший способ заставить ваш код не работать. - person Vatine; 04.04.2013
comment
@binaryjc Основная проблема сейчас - это ЕСЛИ в вашей функции. IF требует, чтобы каждая ветвь содержала только одну форму, в то время как вы пытаетесь оценить две формы, когда тест верен. Попробуйте изменить два последних IF на WHEN или добавить PROGN. Это более ясно, когда код правильно отформатирован. - person Terje D.; 05.04.2013
comment
измените ЕСЛИ на КОГДА сработало. но в конце выводится NIL. это из-за условия, что если он уже напечатал N простых чисел? - person binaryjc; 05.04.2013
comment
@binyryjc Nil — это возвращаемое значение функции. Когда найдено желаемое количество простых чисел, счетчик сбрасывается в последнем when, и по мере раскручивания рекурсии тест в этой форме when терпит неудачу и возвращается nil. Для перезаписи простых чисел: см. мой ответ. - person Terje D.; 05.04.2013

arrow_upward
3
arrow_downward

Чтобы расширить ответ Vatines:

Возможен вариант перезаписи функции prime-numbers с использованием того же алгоритма, но без использования глобальных переменных.

(defun prime-numbers (num &optional (from 2))
   (cond ((<= num 0) nil)
         ((is-prime from) (cons from (prime-numbers (1- num) (1+ from))))
         (t (prime-numbers num (1+ from)))))

Эта функция также возвращает простые числа, а не печатает их.

Проблема с этим рекурсивным решением заключается в том, что оно потребляет стек для каждого найденного/проверенного простого числа. Таким образом, пространство стека может быть исчерпано для больших значений num.

Нерекурсивный вариант

(defun prime-numbers (num &optional (start 2))
   (loop for n upfrom start
         when (is-prime n)
         sum 1 into count
         and collect n
         until (>= count num)))
person Terje D.    schedule 05.04.2013