Форум программистов, компьютерный форум, киберфорум
Наши страницы
Clojure
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
helter
3839 / 2865 / 310
Регистрация: 12.03.2013
Сообщений: 5,199
1

Итерация по простым числам

02.04.2017, 22:32. Просмотров 621. Ответов 9

Уже давно написал я немного кода для итерации по простым числам: НОД и НОК Там ошибочка в макросе. Исправленный вариант:
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
40
(defpackage #:doprimes
  (:use #:cl)
  (:export #:doprimes))
 
(in-package #:doprimes)
 
(defparameter *primes* (make-array 1
                                   :initial-element 2
                                   :fill-pointer 1
                                   :adjustable t))
 
(defun add-prime ()
  (flet ((primep (i) ; caution!  only works here
           (let ((maxbound (floor (sqrt i))))
             (loop for p across *primes*
                   when (> p maxbound) return t
                   never (zerop (mod i p))))))
    (loop for i upfrom (1+ (aref *primes* (- (length *primes*) 1)))
          until (primep i)
          finally (vector-push-extend i *primes*))))
 
(defun get-prime (k)
  (let ((l (length *primes*)))
    (if (< k (length *primes*))
        (aref *primes* k)
        (progn
          (loop repeat (1+ (- k l)) doing (add-prime))
          (aref *primes* k)))))
 
(defmacro doprimes ((p max-bound &optional (result-form nil)) &body body)
  (let ((k (gensym))
        (q (gensym))
        (max (gensym)))
    `(loop with ,p and ,q
           with ,max = ,max-bound
           for ,k upfrom 0
           do (setf ,q (get-prime ,k))
           until (> ,q ,max)
           do (setf ,p ,q) ,@body
           finally (return ,result-form))))
Пример использования:
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(defun factor (n)
  (flet ((prime-factor (n)
           (if (= n 1)
               nil
               (doprimes (p n)
                 (when (zerop (mod n p))
                   (return p))))))
    (loop with p
          for k = n then (/ k p)
          do (setf p (prime-factor k))
          while p collect p)))
 
> (factor 21175)
(5 5 7 11 11)
> (factor 124509)
(3 7 7 7 11 11)
4
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.04.2017, 22:32
Ответы с готовыми решениями:

По трем введенным числам установить, существует ли треугольник со сторонами, равными этим числам
Помогите пожалуйста решить задачи: 1. По трем введенным числам установить, существует ли...

Суммы в горизонтальных линиях должны равняться числам в правой колонке, а в вертикальных - числам в нижней стр
Заполните пустые квадраты, используя только числа от 1 до 9. Суммы в горизонтальных линиях должны...

Прибавить первый элемент ко всем четным числам и последний элемент ко всем нечетным числам
В массиве S(9) прибавить первый элемент ко всем четным числам и последний элемент ко всем нечетным...

Итерация
Здравствуйте. Очень прошу мне помочь решить пример. Идет подготовка к госу, а так как я заочница...

Итерация
Помогите пожалуйста! Задание. Составить программу вычисления значения функции, разложенной в ряд...

9
helter
3839 / 2865 / 310
Регистрация: 12.03.2013
Сообщений: 5,199
09.04.2017, 16:10  [ТС] 2
Lisp
1
2
3
4
5
6
7
8
9
(defun add-prime ()
  (flet ((primep (i) ; caution!  only works here
           (let ((maxbound (isqrt i)))
             (loop for p across *primes*
                   when (> p maxbound) return t
                   never (zerop (mod i p))))))
    (loop for i upfrom (1+ (aref *primes* (- (length *primes*) 1)))
          until (primep i)
          finally (vector-push-extend i *primes*))))
Заменил (floor (sqrt i)) на (isqrt i), спасибо _sg за идею.
4
nullxdth
1929 / 888 / 70
Регистрация: 12.03.2013
Сообщений: 4,134
10.04.2017, 23:55 3
helter, можно определить *primes* как defvar, что бы при повторной загрузки пакета кэш не сбрасывался

Добавлено через 3 минуты
Можно также не определять значение &optional аргумента в nil. Он и так nil, по умолчанию.

Добавлено через 7 минут
Но, самое важное, loop протёк:
Lisp
1
2
(doprimes (x 1)
  finally (return :yoba))
2
helter
3839 / 2865 / 310
Регистрация: 12.03.2013
Сообщений: 5,199
11.04.2017, 14:24  [ТС] 4
Цитата Сообщение от nullxdth Посмотреть сообщение
Но, самое важное, loop протёк:
Это ужасно. Надо переписывать.
0
11.04.2017, 14:24
Shamil1
Модератор
2326 / 1615 / 363
Регистрация: 26.03.2015
Сообщений: 5,880
11.04.2017, 15:19 5
Я использую вот такой вариант на Clojure:
Lisp
1
2
3
4
5
6
7
(defn primes []
    (let [sieve (fn sieve [dic n] 
            (if-let [factors (dic n)]
                (recur (reduce #(update % (+ n %2) (fnil conj []) %2)
                            (dissoc dic n) factors) (inc n))
                (lazy-seq (cons n (sieve (assoc dic (* n n) [n]) (inc n))))))]
        (sieve {} 2)))
http://ideone.com/fyo5yQ
5
ntlinuxnt
$ su
1598 / 513 / 97
Регистрация: 18.11.2010
Сообщений: 2,806
Записей в блоге: 2
Завершенные тесты: 5
11.04.2017, 23:13 6
Lisp
1
2
3
4
5
6
7
(defn sieve [s]
  (cons (first s)
        (lazy-seq (sieve (filter #(not= 0 (mod % (first s)))
                                 (rest s))))))
 
;user=> (take 20 (sieve (iterate inc 2)))
;(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71)
Тоже на Clojure с помощью ленивой последовательности, но не очень оптимизировано.
4
_JohnSmith
117 / 53 / 2
Регистрация: 12.02.2017
Сообщений: 194
12.04.2017, 00:45 7
Цитата Сообщение от Shamil1 Посмотреть сообщение
Я использую вот такой вариант на Clojure
Позвольте поинтересоваться где Вы используете такой вариант? Если не сложно, коротко. Не "на работе", а "в таком-то проекте".
0
Shamil1
Модератор
2326 / 1615 / 363
Регистрация: 26.03.2015
Сообщений: 5,880
12.04.2017, 08:50 8
Цитата Сообщение от _JohnSmith Посмотреть сообщение
Позвольте поинтересоваться где Вы используете такой вариант? Если не сложно, коротко. Не "на работе", а "в таком-то проекте".
Для решения различных задачек по информатике.

Последние две:
Задача "Игра", динамическое программирование
Задача "Радость информатика"
1
Shamil1
Модератор
2326 / 1615 / 363
Регистрация: 26.03.2015
Сообщений: 5,880
12.04.2017, 09:20 9
Цитата Сообщение от ntlinuxnt Посмотреть сообщение
Тоже на Clojure с помощью ленивой последовательности, но не очень оптимизировано.
По сути это не решето, а "наивный" алгоритм: каждое из чисел делим на все предшествующие ему простые числа. Настоящее решето не использует деление (только сложение и возведение в квадрат).
0
helter
3839 / 2865 / 310
Регистрация: 12.03.2013
Сообщений: 5,199
14.07.2017, 23:05  [ТС] 10
Долго ли, коротко ли... Простой loop, вроде выглядит нормально.
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
40
41
42
43
(defpackage #:doprimes
  (:use #:cl)
  (:export #:doprimes))
 
(in-package #:doprimes)
 
(defparameter *primes* (make-array 1
                                   :initial-element 2
                                   :fill-pointer 1
                                   :adjustable t))
 
(defun add-prime ()
  (flet ((primep (i) ; caution!  only works here
           (let ((maxbound (floor (sqrt i))))
             (loop for p across *primes*
                   when (> p maxbound) return t
                   never (zerop (mod i p))))))
    (loop for i upfrom (1+ (aref *primes* (- (length *primes*) 1)))
          until (primep i)
          finally (vector-push-extend i *primes*))))
 
(defun get-prime (k)
  (let ((l (length *primes*)))
    (if (< k (length *primes*))
        (aref *primes* k)
        (progn
          (loop repeat (1+ (- k l)) doing (add-prime))
          (aref *primes* k)))))
 
(defmacro doprimes ((p max-bound &optional result-form) &body body)
  (let ((k (gensym))
        (q (gensym))
        (max (gensym)))
    `(let ((,max ,max-bound)
           (,k -1)
           (,p 1)
           ,q)
       (loop
         (setf ,q (get-prime (incf ,k)))
         (when (> ,q ,max)
           (return ,result-form))
         (setf ,p ,q)
         ,@body))))
2
14.07.2017, 23:05
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.07.2017, 23:05

Итерация
Есть программа для итерационного метода (вариант 2) Но неправильно условие until Не могли бы...

Итерация
Здравствуйте! for(i=0.1; i&lt;=n; i+=0.1) { cout &lt;&lt; i &lt;&lt; &quot; &quot;; } ...

Итерация по документам
всем, добрый день! Помогите, пожалуйста, с таким вопросом - Есть база, каждый документ которой...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru