质数:这是什么lisp,换成AutoLisp是什么模样?

/db_自贡黄明儒_

;;质数列表
(defun prime (n)
   (loop with L = ( loop for i from 2 to n collect i)
       for i in L   
       collect i
       do (delete-if #'(lambda(x) (= 0 (mod x i))) L)) )  (prime 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)

ll_j

自己写了一个，哪位有兴趣可以简化一下：

1. (defun prime (n / l m k i x)
   
2.   (setq l '(2)
   
3.         m l
   
4.         i 2
   
5.   )
   
6.   (while (<= i n)
   
7.     (setq i (1+ i)
   
8.           k (car l)
   
9.           m (cdr l)
   
10.     )
    
11.     (while (and (/= (setq x (rem i k)) 0) m)
    
12.       (setq k (car m)
    
13.             m (cdr m)
    
14.       )
    
15.     )
    
16.     (if (/= x 0)
    
17.       (setq l (cons i l))
    
18.     )
    
19.   )
    
20.   (reverse l)
    
21. )

(defun prime (n / l m k i x)<br />   (setq l '(2)<br />         m l<br />         i 2<br />   )<br />   (while (<= i n)<br />     (setq i (1+ i)<br />           k (car l)<br />           m (cdr l)<br />     )<br />     (while (and (/= (setq x (rem i k)) 0) m)<br />       (setq k (car m)<br />             m (cdr m)<br />       )<br />     )<br />     (if (/= x 0)<br />       (setq l (cons i l))<br />     )<br />   )<br />   (reverse l)<br /> )

原理很简单，从基本的质数2开始，构建表L，以后每个数依次除以L中的元素，都除不尽就是质数，再加入L，依次...

HLCAD

我记得在大学的微机课中，自己额外用BASIC语言编了一个，唉，过去了n年了。

Highflybird

/db_自贡黄明 ：我在小学学过，一直不知道质数有什么用处。几十年过去了.......
现在的被广泛使用的加密算法RSA加密算法，就是基于 因数分解的算法，这跟质数判断算法有很大关系。
你说有质数在现代的计算机的重要性处于什么位置？

newer

ll_j 发表于 2014-11-7 15:30
自己写了一个，哪位有兴趣可以简化一下：

原理很简单，从基本的质数2开始，构建表L，以后每个数依次除以 ...

检查一个数A是否是质数，只要从3往上+2看能否整除，直到这个的平方根

因为如果一直到Sqrt(A)一直没有能整除的话，检查超过Sqrt的部分也是没有必要的，那个肯定是个质数。

这样改进之后的算法复杂度，降低很多

ll_j

newer 发表于 2014-11-7 22:55
检查一个数A是否是质数，只要从3往上+2看能否整除，直到这个的平方根

因为如果一直到Sqrt ...

谢谢指点，改了一下程序：

1. (defun prime (n / l m k i x)
   
2. ;  (setq t1 (getvar "cdate"))
   
3.   (setq l '(3)
   
4.         m l
   
5.         i 3
   
6.   )
   
7.   (while (< i (- n 1))
   
8.     (setq i (+ i 2)
   
9.           k (car l)
   
10.           m (cdr l)
    
11.     )
    
12.     (while (and (/= (setq x (rem i k)) 0) (< k (sqrt i)) m)
    
13.       (setq k (car m)
    
14.             m (cdr m)
    
15.       )
    
16.     )
    
17.     (if (/= x 0)
    
18. ;      (setq l (reverse (cons i (reverse l))))
    
19.       (setq l (append l (list i)))
    
20.     )
    
21.   )
    
22. ;  (setq tt (- (getvar "cdate") t1))
    
23.   (cons 2 l)
    
24. )

(defun prime (n / l m k i x)<br /> ;  (setq t1 (getvar "cdate"))<br />   (setq l '(3)<br />         m l<br />         i 3<br />   )<br />   (while (< i (- n 1))<br />     (setq i (+ i 2)<br />           k (car l)<br />           m (cdr l)<br />     )<br />     (while (and (/= (setq x (rem i k)) 0) (< k (sqrt i)) m)<br />       (setq k (car m)<br />             m (cdr m)<br />       )<br />     )<br />     (if (/= x 0)<br /> ;      (setq l (reverse (cons i (reverse l))))<br />       (setq l (append l (list i)))<br />     )<br />   )<br /> ;  (setq tt (- (getvar "cdate") t1))<br />   (cons 2 l)<br /> )

/db_自贡黄明儒_

ll_j 发表于 2014-11-8 08:16
谢谢指点，改了一下程序：

我认为你上面 的那个已经写得很妙了，没想到还可以简化
今天是怎么了(setq l (append l (list i)))为什么改成(setq l (cons i l))就不行呢？

ll_j

/db_自贡黄明儒_ 发表于 2014-11-10 09:02
我认为你上面 的那个已经写得很妙了，没想到还可以简化
今天是怎么了(setq l (append l (list i)))为什 ...

(cons i l)是从大往小排列，第一个元素是离i最近的质数，(< k (sqrt i))不成立，就退出判断，所以不行。

/db_自贡黄明儒_

ll_j 发表于 2014-11-10 09:10
(cons i l)是从大往小排列，第一个元素是离i最近的质数，(< k (sqrt i))不成立，就退出判断，所以不行。

据说append比cons慢，按理说改这一句没有问题，它在while之外

newer

/db_自贡黄明儒_ 发表于 2014-11-10 09:15
据说append比cons慢，按理说改这一句没有问题，它在while之外

那要看  i 是什么了

命令: (setq a '(1 2) b '(3 4))
(3 4)

命令: (cons a b)
((1 2) 3 4)

命令: (append a b)
(1 2 3 4)


命令: (append a (list b))
(1 2 (3 4))

/db_自贡黄明儒_

newer 发表于 2014-11-10 09:18
那要看  i 是什么了

命令: (setq a '(1 2) b '(3 4))

不是你说的这个问题，现在我明白了，是在第一个while这内。

ll_j

/db_自贡黄明儒_ 发表于 2014-11-10 09:15
据说append比cons慢，按理说改这一句没有问题，它在while之外

单单从函数来说，append是比cons慢，这是因为两者的级别不同，换句话说，cons是基本函数，append是衍生函数，不仅如此，append可能还加了容错处理，速度更慢（论坛以前讨论过，自己构造的append比系统的还快）。
但在运用中不能受这个框框限制，我在代码中给出了两个构造表的方法，速度大体相近，用cons的难免要使用reverse，速度也就降下来了。
这里的append是在while中的，但只是有限次的循环（表中质数数量），所以即使速度慢，也是有限的，这点速度影响，对质数算法的累加来说，可以忽略。
另一个帖子中，鸟兄有一段质数的判断，我加了个头试试，速度的确比这里的代码快，但遗憾的是，只能算到58441，后面就没有了，鸟兄的代码中使用了逻辑位移，不明白他的算法的确看不懂，只好作罢。

newer

ll_j 发表于 2014-11-10 09:44
单单从函数来说，append是比cons慢，这是因为两者的级别不同，换句话说，cons是基本函数，append是衍生函 ...

APPEND比CONS慢是因为链表的存储结构确定的，ACAD的LIST是单向链表结构，如果你只APPEND一个元素，那么APPEND和CONS速度是一样的

(append '(1) '(1 2 3 4)) == (cons 1 '(1 2 3 4)))

APPEND的速度快慢，是由第一个表的长度决定的，和第二个表无关，操作APPEND和CONS都是在第二个表头插入操作，直接就能寻址到。

如果第一个表的长度很长很长的时候，APPEND操作需要遍历第一个表到表尾，得到指针后链接到第二个表头上。

所以，对你写的这个应用来说，APPEND和CONS没什么太大的区别。

newer

ll_j 发表于 2014-11-10 09:44
单单从函数来说，append是比cons慢，这是因为两者的级别不同，换句话说，cons是基本函数，append是衍生函 ...

对你说的 移位 操作，是机器码的大小长短决定了运行的时间

比如，2*2 的操作 要比 2左移一位 的时间要长的多，结果都是4.

所有的数据在机器里面存储的最小单元都是二进制BIT，一个BIT的移位操作要比乘法操作快的多，乘法操作最后都是转为加法操作。

很多时候使用移位操作是在算法复杂度一个级别的情况下，再提高效率的技巧之一。

/db_自贡黄明儒_

newer 发表于 2014-11-10 10:07
APPEND比CONS慢是因为链表的存储结构确定的，ACAD的LIST是单向链表结构，如果你只APPEND一个元素，那么AP ...

N版，你上次您给我讲了boole ,这次是不是给我讲讲lsh的用法 ，我在明经和晓东都搜不到呀{:soso_e109:}