Код Lisp не отвечает

TL;DR: проблема не в памяти, а в скорости.

Вы были очень изобретательны в преодолении недостатка знаний. :) На самом деле, у нас есть progn в Common Lisp, который группирует несколько вычисляемых выражений по порядку:

(defun myprimes-to (n &aux          ;; &aux vars may have init values
                      (current 3)
                      (primecount 1)
                      (isprime t) ; "yes"   ;; t is better 
                      (primes (list 2))
    (loop  ;for x from current do   ;; for a bare loop, just `loop` is enough
      (progn  ;list                 ;; `progn` groups expressions together to be
        (setq isprime t) ; "yes"    ;;    evaluated in order, one after another
        (loop                       ;;      (not even needed here, see comments below)
          for prime in primes do 
            (if (= (mod current prime) 0) 
                (progn  ;list
                  (setq isprime nil) 
                  (return))         ;; exit the loop
                nil))               ;; don't have to have alternative clause
        (if isprime 
            (progn  ;list 
              (incf primecount)  ; (setq primecount (+ primecount 1)) ;; same but shorter
              (setq primes (cons current primes)) 
              (if (= primecount n)  ;; abstract the n as function's argument
                  (return)          ;; exit the loop
                  nil))
            ;; What?? increment your loop var _only_ if it's not prime?
            (setq current (+ current 1)))))
    ;; (write-line (write-to-string primes))
    primes)                         ;; just return them

Поэтому, если current является простым, попытка повторяется. Поскольку в последний раз он был добавлен в primes, теперь он будет считать себя не простым, и итерация продолжится. Результаты правильные, но логика искажена.

Что еще более важно, здесь есть две основные неэффективности с точки зрения алгоритма: вы тестируете все primes до сих пор и обратно. Но у любого заданного числа гораздо больше шансов иметь меньший делитель, чем больший; поэтому мы должны проверять по простым числам в возрастающем порядке. И мы можем остановиться, когда простое число p равно p*p > current, потому что если current == a*b и a <= b, то a*a <= b*a == current. Ранняя остановка дает огромное ускорение, она изменяет сложность времени выполнения с ~ n^2 до, грубо говоря, ~ n^1,5 (в произведенных n простых числах).

Обратите внимание: ваш код хуже, чем ~ n^2, алгоритмически. Было бы ~ n^2, если бы проверялись простые числа в порядке возрастания. -- Почему это важно? Это дает частичный ответ на ваш вопрос: у вас проблемы не с памятью, а с скоростью. Сколько бы времени ни потребовалось вашему коду для завершения n=100, для перехода к n=1000 потребуется более чем в 100 раз (поскольку 1000/100 == 10, а 10^2 = 100). И чтобы добраться до n=10000, потребуется в 100 раз больше времени. Таким образом, если задача n=100 заняла секунду времени выполнения, n=1000 займет 100 секунд (~ 2 минуты), а n=10001 200 минут (более чем через 3 часа).

Мы всегда можем получить оценки порядков роста во время выполнения эмпирически; см. эту статью о WP.

Таким образом, вам нужно поддерживать primes в порядке возрастания и append каждого нового простого числа до конца за время O(1). Вам нужно добиться тех же результатов, что и строка кода (setq primes (append primes (list current))); но вы не можете использовать эту строку кода, потому что это O (n) по времени и резко замедлит работу всей программы. То же самое с (setq primes (reverse (cons current (reverse primes)))). И мы не можем поддерживать primes в обратном порядке, потому что мы должны тестировать в порядке возрастания, и простой вызов (reverse primes) для каждого нового current также является операцией времени O(n).

Решение состоит в том, чтобы использовать rplacd: (rplacd (last primes) (list current)). Даже это все равно неправильно, потому что last тоже операция O(n). Вместо этого вам придется поддерживать дополнительную переменную, указывающую на последнюю cons-ячейку списка простых чисел, и продвигать ее каждый раз, когда вы добавляете туда новое простое число: (setq last_cell (cdr last_cell)).

Когда вы запустите фиксированный код, вы обнаружите, что он завершает задание 10 000 примерно за 0,1 секунды и работает примерно за ~ n^1,4 порядки роста во время выполнения в этом диапазоне.

Вы можете объяснить

• что за переменная X и почему она не используется?

• что делают звонки LIST?

• зачем вы используете все эти глобальные переменные?

• почему вы не определяете никаких функций?

• почему код перебирает все простые числа?

Вот рефакторинг и немного улучшенная версия, основанная на вашем коде:

(defun find-primes (n &aux (primes (list 2)) (l-primes primes) (n-primes 1))
  "returns a list of the first n primes"
  (flet ((prime-p (i &aux (limit (isqrt i)))
           "returns T if i is a prime number"
           (loop for prime in primes
                 until (> prime limit)
                 when (zerop (mod i prime))
                 do (return-from prime-p nil))
           t))
    (loop for i from 3
          until (>= n-primes n)
          do (when (prime-p i)
               (setf (cdr l-primes) (list i)
                     l-primes (cdr l-primes))
               (incf n-primes))))
  primes)

(print (find-primes 10000))

Особенности вышеуказанной функции:

• он хранит список простых чисел, увеличивая
• он сохраняет ссылку на последние cons списка простых чисел, чтобы эффективно добавлять в конец списка
• у него есть предикатная подфункция prime-p, которая возвращает T, если число является простым
• предикат использует функцию isqrt для ограничения числа для поиска

С проверкой на N и локальным макросом для проталкивания в конец это выглядит так:

(defun find-primes (n &aux (primes (list 2)) (l-primes primes) (n-primes 1))
  "returns a list of the first n primes"
  (check-type n (integer 1))
  (flet ((prime-p (i &aux (limit (isqrt i)))
           "returns T if i is a prime number"
           (loop for prime in primes
                 until (> prime limit)
                 when (zerop (mod i prime))
                 do (return-from prime-p nil))
           t))
    (macrolet ((push-last (obj place)
                 `(setf (cdr ,place) (list ,obj)
                        ,place (cdr ,place))))
      (loop for i from 3
            until (>= n-primes n)
            do (when (prime-p i)
                 (push-last i l-primes)
                 (incf n-primes)))))
  primes)

Давай попробуем:

CL-USER 3 > (time (find-primes 10000))
Timing the evaluation of (FIND-PRIMES 10000)

User time    =        0.052
System time  =        0.000
Elapsed time =        0.044
Allocation   = 292192 bytes

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

Я немного переписал:

(defvar current)
(setf current 3)
(defvar primecount)
(setf primecount 1)
(defvar primes)
(setf primes (list 2))
(defvar isprime)

(loop for x from current do
  (setq isprime t)
  (loop 
    for prime in primes do 
      (when (zerop (mod current prime))
        (setq isprime nil) (return)))
  (if isprime 
      (progn 
        (incf primecount)
        (push current primes)
        (when (= primecount 10001) 
          (return)))
      (incf current)))
(write-line (write-to-string primes))

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

Ваша программа работает в моем SBCL для 10001 следующим образом (обернутая в функцию выполнения):

CL-USER> (time (do-stuff))
Evaluation took:
  13.486 seconds of real time
  13.438000 seconds of total run time (13.437000 user, 0.001000 system)
  99.64% CPU
  40,470,003,369 processor cycles
  1,674,208 bytes consed

CL-USER> (room)
Dynamic space usage is:   134,466,112 bytes.
Read-only space usage is:      5,856 bytes.
Static space usage is:         4,032 bytes.
Control stack usage is:        8,808 bytes.
Binding stack usage is:        1,056 bytes.
Control and binding stack usage is for the current thread only.
Garbage collection is currently enabled.

Breakdown for dynamic space:
  45,803,376 bytes for   569,191 instance objects.
  22,831,488 bytes for 1,426,968 cons objects.
  16,472,576 bytes for    16,135 code objects.
  15,746,176 bytes for   130,439 simple-vector objects.
  13,794,096 bytes for    36,381 simple-character-string objects.
  19,850,400 bytes for   440,297 other objects.
  134,498,112 bytes for 2,619,411 dynamic objects (space total.)