正则表达式判断是否质数，是真的吗？

/db_自贡黄明儒_ · 发表于 2014-11-7 14:00:16

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

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

×

http://zhan.renren.com/lisper?gi ... 50&checked=true
正则表达式判断是否质数，是真的吗？

Highflybird · 发表于 2014-11-7 15:29:10

本帖最后由 Highflybird 于 2014-11-7 15:35 编辑

这个只不过是小范围内的判断。一个不超过1000，一个不超过100，这个对实际没多少用途.
下面是我的质数判断代码。

(defun IsPrime (p)
(if (> p 13)
(cond
( (or (= (rem p 2) 0)
(= (rem p 3) 0)
(= (rem p 5) 0)
(= (rem p 7) 0)
(= (rem p 11) 0)
(= (rem p 13) 0)
)
nil
)
( (and (RabbinMiller 2 p)
(RabbinMiller 7 p)
(RabbinMiller 5 p)
)
T
)
(t nil)
)
(and (member p '(2 3 5 7 11 13)))
)
)
(defun paw_mod( bs power diver)
(cond
((zerop power)
1
)
((= power 1)
bs
)
((= (rem power 2) 0)
(paw_mod (rem (* bs bs) diver) (lsh power -1) diver)
)
(t
(rem (* (paw_mod (rem (* bs bs) diver) (/ power 2) diver) bs) diver)
)
)
)
(defun RabbinMiller (base num / D K N RET TT)
(setq n (1- num))
(setq d n)
(while (= (rem d 2) 0)
(setq d (lsh d -1))
)
(setq k (paw_mod base d num))
(if (or (= k 1) (= k n))
t
(progn
(setq tt (/ n 2))
(while (/= d tt)
(setq d (lsh d 1))
(if (= (paw_mod base d num) n)
(setq ret t
d tt
)
)
ret
)
)
)
)

(defun IsPrime (p) 
  (if (> p 13) 
    (cond 
      ( (or (= (rem p 2) 0) 
            (= (rem p 3) 0) 
            (= (rem p 5) 0) 
            (= (rem p 7) 0) 
            (= (rem p 11) 0) 
            (= (rem p 13) 0) 
        ) 
        nil 
      ) 
      ( (and (RabbinMiller 2 p) 
             (RabbinMiller 7 p) 
             (RabbinMiller 5 p) 
        ) 
        T 
      ) 
      (t nil) 
    ) 
    (and (member p '(2 3 5 7 11 13))) 
  ) 
) 
 
(defun paw_mod( bs power diver) 
  (cond 
    ((zerop power) 
     1 
    ) 
    ((= power 1) 
     bs 
    ) 
    ((= (rem power 2) 0) 
     (paw_mod (rem (* bs bs) diver) (lsh power -1) diver) 
    ) 
    (t 
      (rem (* (paw_mod (rem (* bs bs) diver) (/ power 2) diver) bs) diver) 
    ) 
  ) 
) 
 
(defun RabbinMiller (base num / D K N RET TT) 
  (setq n (1- num)) 
  (setq d n) 
  (while (= (rem d 2) 0) 
    (setq d (lsh d -1)) 
  ) 
  (setq k (paw_mod base d num)) 
  (if (or (= k 1) (= k n)) 
    t 
    (progn 
      (setq tt (/ n 2)) 
      (while (/= d tt) 
        (setq d (lsh d 1)) 
        (if (= (paw_mod base d num) n) 
          (setq        ret t 
                d tt 
          ) 
        ) 
        ret 
      ) 
    ) 
  ) 
)

譬如： (IsPrime 12323) ==>T
(IsPrime 23111) ==> nil

duotu007 · 发表于 2014-11-8 13:25:46

49069 49081 49103 49109 49117 49121 49123 49139 49157 49169
49171 49177 49193 49199 49201 49207 49211 49223 49253 49261
49277 49279 49297 49307 49331 49333 49339 49363 49367 49369
49391 49393 49409 49411 49417 49429 49433 49451 49459 49463
49477 49481 49499 49523 49529 49531 49537 49547 49549 49559
49597 49603 49613 49627 49633 49639 49663 49667 49669 49681
49697 49711 49727 49739 49741 49747 49757 49783 49787 49789
49801 49807 49811 49823 49831 49843 49853 49871 49877 49891
49919 49921 49927 49937 49939 49943 49957 49991 49993 49999
函数通不过

/db_自贡黄明儒_ · 发表于 2014-11-10 08:58:45

Highflybird 发表于 2014-11-7 15:29
这个只不过是小范围内的判断。一个不超过1000，一个不超过100，这个对实际没多少用途.
下面是我的质数判断 ...

(IsPrime 49069)=》nil 这个确实有问题。大师用了lsh ,这个函数看不懂了。

ll_j · 发表于 2014-11-10 09:50:58

(defun tt (n)
(setq l '(3 2)
i 3
)
(while (< i (- n 1))
(setq i (+ i 2))
(if (isprime i)
(setq l (cons i l))
)
)
(reverse l)
)

给鸟兄的加了这段代码进行捕捉，发现超过58441就无法判别了，算法不懂，看代码无法看，只好作罢。

Highflybird · 发表于 2014-11-10 11:32:39

恩，存在bug，我以后调整看看。

Highflybird · 发表于 2014-11-10 11:45:42

/db_自贡黄明儒_ 发表于 2014-11-10 08:58
(IsPrime 49069)=》nil 这个确实有问题。大师用了lsh ,这个函数看不懂了。

lsh 就相当于二进制移位，譬如 (lsh 3 10) ==> 3* (2^10) 左移位
(lsh 48 -2) ==> 48/ (2^2) 右移位

/db_自贡黄明儒_ · 发表于 2014-11-13 13:21:47

Highflybird 发表于 2014-11-10 11:45
lsh 就相当于二进制移位，譬如 (lsh 3 10) ==> 3* (2^10) 左移位
(lsh 48 -2) ==> 48/ ( ...

运行时间比较

;;[功能] 是否质数
;;(Is-Prime 49069)=>T
(defun Is-Prime (n / FLAG I ROOT)
(cond
((<= n 20)
(cond ((member n '(2 3 5 7 11 13 17 19)) T))
)
((= (rem n 2) 0) nil)
(T
(setq root (sqrt n))
(setq i 1)
(while (and (<= (setq i (+ i 2)) root) (setq Flag (/= (rem n i) 0))))
Flag
)
)
)
(defun C:w1 (/ T1)
(setq t1 (getvar "cdate"))
(Repeat 1000 (IsPrime 49069))
(PRINC(- (getvar "cdate") t1))
(PRINC)
)
(defun C:w2 (/ T1)
(setq t1 (getvar "cdate"))
(Repeat 1000 (Is-Prime 49069))
(PRINC(- (getvar "cdate") t1))
(PRINC)
)

Command:
Command: w1 9.31323e-008

Command:
Command: w2 1.08033e-007

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

[研讨] 正则表达式判断是否质数，是真的吗？

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

点评

评分

点评

点评

评分