Определить рекурсивную функцию

@Luz · Регистрация: 24.02.2015

Студворк — интернет-сервис помощи студентам

Всем привет, нужна помощь... нужно написать рекурсивную функцию которая для заданного n вернет соответствующее простое число, то есть f(1) = 2, f(2) = 3 и так далее...

transformator.t · 24.02.2015, 19:43

Luz, привет! ты недооформил пост, забыл показать наработки свои))

@helter · 24.02.2015, 20:43

Ещё алгоритм неплохо бы, а то ничего не приходит в голову, кроме как перебирать числа и смотреть, простые они или нет. Можно написать что-нибудь на псевдокоде.

@Catstail · 24.02.2015, 21:30

Итерационное решение:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
(defun is-prime (n)
  (cond  ((<= n 3) t)
         ((evenp n) nil)
         (t (iter (for i from 3 to (\ n 2) by 2)
                  (when (zerop (% n i)) (return nil)) t))))
 
(defun prime-by-num (n)
  (let ((k 0))
   (iter (for i upfrom 2)
     (when (is-prime i) 
       (counting i into k)
       (when (>= k n) (return i))))))
 
==> prime-by-num
 
(prime-by-num 1)
 
==> 2
 
(prime-by-num 2)
 
==> 3
 
(prime-by-num 3)
 
==> 5
 
(prime-by-num 20)
 
==> 71

Добавлено через 18 минут
А вот рекурсивное:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
(defun is-prime (n &optional (p 3) (k (/ n 2)))
  (cond ((<= n 2) t)
        ((evenp n) nil)
        ((> p k) t)
        ((zerop (rem n p)) nil)
        (t (is-prime n (+ p 2) k))))
 
 
(defun prime-by-num (n &optional (q 3) (k 2)) 
  (cond  ((= n 1) 2)
         ((= n 2) 3)
         ((is-prime q) 
         (cond ((= k n) q)
               (t (prime-by-num n (+ q 2) (+ k 1)))))
        (t (prime-by-num n (+ q 2) k))))
 
==> prime-by-num
 
(prime-by-num 3)
 
==> 5
 
(prime-by-num 4)
 
==> 7
 
(prime-by-num 1)
 
==> 2
 
(prime-by-num 2)
 
==> 3
 
(prime-by-num 20)
 
==> 71

Добавлено через 10 минут
А вот генератор простых (не слишком оптимальный...):

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
(let ((prime 1))
   (defun reset-prime () (setq prime 1))
   (defun next-prime ()
     (setq prime (+ 1 prime))
     (if (is-prime prime) prime (next-prime))))
 
==> next-prime
 
(next-prime)
 
==> 2
 
(next-prime)
 
==> 3
 
(next-prime)
 
==> 5
 
(next-prime)
 
==> 7
 
(next-prime)
 
==> 11
 
(next-prime)
 
==> 13
 
(reset-prime)
 
==> 1
 
(next-prime)
 
==> 2

@_sg · 24.02.2015, 23:53

Lisp
1
2
3
4
5
6
7
8
9
10
11
(defun n-prime (n &optional (c 1) (m 3) (ac '(2)))
  (cond ((= c n) (- m 2))
        ((loop for a in ac never (zerop (rem m a)))
         (n-prime n (1+ c) (+ m 2) (cons m ac)))
        (t (n-prime n c (+ m 2) ac))))
 
> (time (n-prime 10001))
Real time: 87.91196 sec.
Run time: 87.641365 sec.
Space: 80000 Bytes
104743

Добавлено через 21 секунду

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
(defun primep (n &aux (m 1))
  (loop while (< (* m m) n) never (zerop (rem n (incf m)))))
          
(defun n-prime (n &aux (c 1) (m 2))
  (loop while (< c n) do (when (primep (incf m)) (incf c))
        finally (return m)))
 
> (time (n-prime 10001))
Real time: 1.5756028 sec.
Run time: 1.57561 sec.
Space: 0 Bytes
104743

Добавлено через 12 минут

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
(defun check (x)
  (when (> x 1) (loop for i from 2 to (isqrt x)
                      never (zerop (mod x i)))))
 
(defun primes (n m &optional w) 
  (cond ((= n m) (nreverse w))
        ((or (= n 2) (check n)) (primes (1+ n) m (cons n w)))
        ((primes (1+ n) m w))))
 
> (primes 1 30)
(2 3 5 7 11 13 17 19 23 29)
> (primes 6 30)
(7 11 13 17 19 23 29)

Добавлено через 20 секунд

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
(defun primes(x n &optional w) 
  (cond ((= x n) (nreverse w))
        ((or (= x 2) (when (> x 1)
                       (loop for i from 2 to (isqrt x)
                             never (zerop (mod x i)))))
         (primes (1+ x) n (cons x w)))
        ((primes (1+ x) n w))))
 
> (primes 1 30)
(2 3 5 7 11 13 17 19 23 29)
> (primes 6 30)
(7 11 13 17 19 23 29)

Добавлено через 30 секунд

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
(defun check (n)
  (when (> n 1) (loop for a from 2 to (isqrt n)
                      never (zerop (mod n a)))))
 
(defun primes(n m) 
  (loop for a from n to m
        when (or (= a 2) (check a)) collect a))
 
> (primes 1 30)
(2 3 5 7 11 13 17 19 23 29)
> (primes 6 30)
(7 11 13 17 19 23 29)

Добавлено через 10 минут

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
(defun check (n)
  (when (> n 1) (loop for a from 2 to (isqrt n)
                      never (zerop (mod n a)))))
 
(defun primes(n m) 
  (loop for a from n to m
        when (or (check a) (= a 2)) collect a))
 
> (primes 1 30)
(2 3 5 7 11 13 17 19 23 29)
> (primes 6 30)
(7 11 13 17 19 23 29)

Добавлено через 9 минут

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(defun check (n)
  (when (> n 1) (loop for a from 2 to (isqrt n)
                      never (zerop (mod n a)))))
 
(defun primes (n m)
  (if (> n 2)
      (loop for a from n to m
            when (check a) collect a)
      (cons 2 (loop for a from n to m
                    when (check a) collect a))))
 
> (primes 1 30)
(2 3 5 7 11 13 17 19 23 29)
> (primes 6 30)
(7 11 13 17 19 23 29)

@Luz · 26.02.2015, 23:13 **[ТС]**

Catstail, спасибо за решение)))

@castorsky · 04.03.2015, 09:10

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
;; racket-lang.org
(define PRIMES '(5 3 2))
 
(define (next-prime)
  (let loop ((n (+ 2 (car PRIMES))))
    (if (member 0 (map (lambda (i) (remainder n i)) PRIMES))
        (loop (+ 2 n))
        (begin
          (set! PRIMES (cons n PRIMES))
          n))))
 
(define (foo n (len (length PRIMES)))
  (let/cc return
    (when (<= n 0) (return -1))
    (when (<= n len) (return (car (take-right PRIMES n))))
    (return (for/fold ([acc 0])
                      ([i (- n len)])
              (next-prime)))))
 
> (map foo (range 20))
'(-1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67)
>

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .

@Luz 0 / 0 / 0 Регистрация: 24.02.2015 Сообщений: 2

	Определить рекурсивную функцию 24.02.2015, 19:21. Показов 1358. Ответов 6 Метки нет (Все метки) Всем привет, нужна помощь... нужно написать рекурсивную функцию которая для заданного n вернет соответствующее простое число, то есть f(1) = 2, f(2) = 3 и так далее... 0

transformator.t defun 603 / 617 / 44 Регистрация: 30.04.2011 Сообщений: 702
	24.02.2015, 19:43
	Luz, привет! ты недооформил пост, забыл показать наработки свои)) 5

@helter 4528 / 3522 / 358 Регистрация: 12.03.2013 Сообщений: 6,038
	24.02.2015, 20:43
	Ещё алгоритм неплохо бы, а то ничего не приходит в голову, кроме как перебирать числа и смотреть, простые они или нет. Можно написать что-нибудь на псевдокоде. 2

@Luz 0 / 0 / 0 Регистрация: 24.02.2015 Сообщений: 2
	26.02.2015, 23:13 [ТС]
	Catstail, спасибо за решение))) 0

Определить рекурсивную функцию

Решение