求n以内素数的递归算法及筛法

aimisiyou · 发表于 2015-1-22 20:41:38

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

×

本帖最后由 aimisiyou 于 2015-1-23 18:13 编辑

;;;递归算法
(defun f (n)
   (if (= n 2)
      (setq va (list 2))
      (if (= n 3)
         (setq va (list 3 2))
         (if (= n 4)
            (setq va (list 3 2))
            (if (= n 5)
                  (setq va (list 5 3 2))
                  (if (= (apply '* (mapcar '(lambda (x) (rem n x)) (f (fix (sqrt n))))) 0)
                     (if (> (rem n 6) 1)
                        (setq va (f (- n -1 (rem n 6))))
                        (setq va (f (- n 1 (rem n 6))))
                     )
                     (if (= (rem n 6) 5)
                     (setq va (cons n (f (- n -1 (rem n 6)))))
                     (setq va (cons n (f (- n 1 (rem n 6)))))
                     )
                  )
            )
         )
      )
   )
  va
)
(reverse (f 10000))

;;;筛法
(defun f (n)
(setq i 3 lst nil)
(while (<= i n)
      (setq lst (cons i lst))
      (setq i (+ i 2))
)
  (setq llst (cons (list 2) (reverse lst)))
  (while (and (< (car (car llst)) (sqrt n) ) (< (cadr llst) (sqrt n)) )
      (setq flst (cons (cadr llst) (car llst)))
      (setq plst (vl-remove-if '(lambda (x) (= (rem x (car flst)) 0)) (cdr llst)))
      (setq llst (cons flst plst))
)
  (setq alst (car llst) blst (cdr llst))
  (mapcar '(lambda (e) (setq blst (cons e blst))) alst)
blst
)
(f 10000)

liyamg · 发表于 2015-4-27 13:27:17

收藏一下，多谢分享

qaxgb · 发表于 2015-10-21 20:31:26

提示: 作者被禁止或删除内容自动屏蔽

aimisiyou · 发表于 2015-10-21 20:59:26

;;;上面的筛法有点复杂，没优化
;;;下面这个好理解
(defun f (n)
  (setq i 3 lst nil)
  (while (<= i n)
      (setq lst (cons i lst))
      (setq i (+ i 2))
)
  (setq llst (cons 2 (reverse lst)))
  (setq flst nil)
  (while (and (/= (cdr llst) nil) (/= (setq c (nth 0 llst)) nil))
   (setq flst (cons c flst))
   (setq llst (vl-remove-if '(lambda (x) (= (rem x c) 0)) (cdr llst)))
  )
  (reverse flst)
)

账号		自动登录	找回密码
密码			立即注册

qaxgb qaxgb 当前离线 UID 753986 积分 14 精华贡献威望活跃度 D豆在线时间小时注册时间 2015-10-13 最后登录 1970-1-1 窥视卡雷达卡	发表于 2015-10-21 20:31:26 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽
	论坛插件加载方法发帖求助前要善用【论坛搜索】功能，那里可能会有你要找的答案；如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请把帖子标题加上【已解决】；如何回报帮助你解决问题的坛友，一个好办法就是给对方加【D豆】，加分不会扣除自己的积分，做一个热心并受欢迎的人！
	回复支持反对使用道具举报

[分享] 求n以内素数的递归算法及筛法

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

浏览过的版块