Модифицированное сито для поиска простых чисел в схеме

Один фрагмент кода, который приводит к зависанию, — это (if ( > (car list) (sqrt (car(reverse list)))), который очень похож на условие цикла, которое вы могли бы использовать в других языках (и слово iterate также намекает на просмотр в других языках).
Я бы порекомендовал вы начинаете сначала, с другой стратегией.

Когда вы работаете со списками, вы обычно хотите рекурсивно использовать только их структуру.

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

(Обратите внимание, что это далеко не так эффективно, как могло бы быть, но это скорее начало работы с рекурсивным уровнем внушения. Прочтите ответ Уилла, чтобы узнать больше.)

Если принять желаемое за действительное и предположить, что существует процедура remove-multiples-of, которая делает то, на что она похожа, это могло бы выглядеть так:

(define (my-sieve-helper ls)
  (if (null? ls)
      '()
      (cons (car ls)
            (my-sieve-helper (remove-multiples-of (car ls) (cdr ls))))))

Итак, remove-multiples-of...
Это то же самое, что хранить все числа, которые не делятся на числа, так что давайте придумаем другую функцию:

(define (remove-multiples-of x ls) (filter (not-divisible-by x) ls))

где (not-divisible-by x) — это процедура, которая принимает число и возвращает, не делится ли это число на x.

(define (not-divisible-by n) (lambda (x) (not (zero? (remainder x n)))))

И теперь мы можем добавить подходящую обертку.
Я сделал так:

(define (from-to m n)
  (if (> m n)
      '()
      (cons m (from-to (+ m 1) n))))

(define (my-sieve n) (my-sieve-helper (from-to 2 n)))

Контрольная работа:

> (my-sieve 100)
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)

Что ж, ваш вопрос представляет собой интересный случай недостаточной спецификации, который может быть выгодным, задерживая фактическую спецификацию, а не просто реализацию, как обычно, подпрограмм, используемых вашим фрагментом кода.

Здесь у нас есть sievehelper, который использует нереализованные неуказанные filterfunc и not-divisible-by. Несмотря на их наводящие на размышления названия, эти функции могут делать что угодно, пока они работают, когда используются вместе, и заставляют функцию, использующую их, sievehelper, также выполнять свою работу, как предполагалось. Отложенная спецификация для победы!

Итак, давайте сначала посмотрим, что может означать sievehelper как данное, что он делает? Предполагая очевидное значение двух подпрограмм, кажется, что она предназначена для выполнения одноэтапной фильтрации своей рабочей последовательности, отбрасывая ее из любых кратных ее головному элементу, который находится в его позиции car.

Это сигнализировало бы об условии остановки, возвращая (). Это условие остановки a*a > z для входного списка [a,b,c,...,z].

В противном случае он не выполняет зацикливание, а только один его шаг. Ваш sieve вообще не учитывает это, поэтому его нужно будет изменить, чтобы он постоянно вызывал этот помощник, выполняя шаг за шагом, как обычно в алгоритмах просеивания, пока квадрат первого элемента не станет больше, чем последний элемент в рабочем алгоритме. последовательность, когда действительно безопасно остановить отбраковку, так как все кратные в последовательности уже будут удалены из нее как кратные меньших простых чисел ...... при условии, что эти меньшие простые числа были присутствуют в исходной последовательности.

Таким образом, это обнаруженное требование относится к третьему нереализованному используемому подмаршруту, makelist. Вы упомянули, что он должен создать список последовательных натуральных чисел от 2 до n, и теперь мы понимаем, зачем нам это нужно.

Итак, чтобы перебирать через различные версии входного списка, поскольку каждый делитель по очереди отфильтровывается из него, используя ваш sievehelper определение как дано, ваша sieve функция должна быть изменена, например, как

(define sieve 
   (lambda (n)
      (let ((init (makelist n)))
        (let loop ((this              init ) 
                   (next (sievehelper init)))
            (if (null? next)
              this
              (cons (car this) 
                    (loop              next 
                          (sievehelper next))))))))

Этот код основан на работе с парой — текущей последовательностью и ее следующей итерацией. На каждом шаге следующая версия списка находится после удаления из него всех кратных его элементу head на sievehelper (включая сам элемент head, следующее найденное простое число) -- или пустой список вместо этого возвращается, чтобы сигнализировать об окончании обработки, когда известно, что все числа в списке уже являются простыми, по построению.

Пробуем в Racket:

> (sieve 50)
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)

(Приведенный выше код включает исправление от ad-absurdum из последующей записи вопросов и ответов к ошибке, которая изначально содержалась в этом коде) .

Чтобы запустить его, необходимо было сделать дополнительные определения:

(define filterfunc filter)

(define (not-divisible-by n)
  (let ((m n))
    (lambda (x)
      (let ((ret (not (= x m))))
         (if (>= x m) (set! m (+ m n)) #f)
         ret))))

(define (makelist n)
  (range 2 (+ 1 n)))   ;; in Racket

Определение not-divisible-by таким, как мы сделали здесь, делает его действительно решетом Эратосфена, работающим только посредством дополнений и сравнений. А ранняя остановка, как и в исходном коде, не позволяет его временной сложности ухудшиться, чем должна.