Преобразование списка в список простых чисел - Lisp

Узнай цену своей работы

Формулировка задачи:

Добрый день! Я в Лиспе совсем новичок, поэтому решение задач пока дается с трудом. Помогите с написанием цикла по простым числам при заданных начальном и конечном значении, т.е. имеем допустим список вида: (1 11) нужно получить из него такой: (2 3 5 7 11) Плюс нужно проверять первичные элементы списка на положительность, т.е. если какой-либо из элементов списка (первый или последний) меньше 1, то возвращаемый список должен быть nil. Функция проверки что число простое есть, да и поиск следующего простого числа тоже уже удалось получить. Пишу на CommonLisp. Заранее буду благодарен за любую помощь.

Решение задачи: «Преобразование списка в список простых чисел»

textual
Листинг программы
(defun is-prime (n &optional (c 2))
  (cond ((= n 1) nil)
        ((<= n 3) t)
        ((> c (/ n 2)) t)
        ((zerop (rem n c)) nil)
        (t (is-prime n (+ c 1))))) 
 
==> IS-PRIME
 
(defun task (beg end &optional (r nil))
  (cond ((or (minusp beg) (minusp end)) nil)
        ((> beg end) r)
        ((is-prime end) (task beg (- end 1) (cons end r)))
        (t (task beg (- end 1) r)))) 
 
==> TASK
 
(task 1 20)
 
==> (2 3 5 7 11 13 17 19)
 
(task 2 66)
 
==> (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61)
 
(task 12 66)
 
==> (13 17 19 23 29 31 37 41 43 47 53 59 61)

Объяснение кода листинга программы

В коде используется функция is-prime, которая проверяет, является ли число простым. Она принимает число n и опциональный аргумент c — число, до которого необходимо проверить, является ли n простым. Если n равно 1, функция возвращает nil, так как 1 не является простым числом. Если n меньше или равно 3, функция возвращает t, так как 2 и 3 являются простыми числами. Если c больше или равно n/2, функция возвращает t, так как n не может быть простым числом. Если n делится нацело на c, функция возвращает nil, так как n не является простым числом. В противном случае функция рекурсивно вызывает саму себя с аргументами n и c+1. Функция task принимает начальное и конечное значение для списка простых чисел, а также опциональный аргумент r — результат выполнения функции, который передается дальше по системе. Если начальное значение больше или равно конечному, функция возвращает r. Если конечное значение является простым числом, функция рекурсивно вызывает саму себя с аргументами начальное значение, уменьшенное на 1, и результат, увеличенный на конечное значение. В противном случае функция рекурсивно вызывает саму себя с аргументами начальное значение, уменьшенное на 1, и r. При вызове функции task с аргументами 1 и 20, она возвращает список простых чисел [2, 3, 5, 7, 11, 13, 17, 19]. При вызове функции task с аргументами 2 и 66, она возвращает список простых чисел [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]. При вызове функции task с аргументами 12 и 66, она возвращает список простых чисел [13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61].

Оцени полезность:

6   голосов , оценка 4 из 5
Похожие ответы