数论: 质数检测相关算法总结

总结一下质数相关的算法, 权当做自己的学习笔记了:

质数检测问题大类分成两类: (1) 给定一个整数, 判断这个整数是不是质数. (2) 求小于等于某一个整数的所有质数. 两类问题都要求判断是否是质数, 一般有如下几种方法:

A. 暴力: 根据质数的定义, 从2开始到n-1枚举t, 如有任何数字可以整出n (n % t == 0), 那么不是质数, 否则这个数字就是质数.

B. 利用定理: 任何一个合数一定存在一个小于等于 n ^ 0.5 的质数因子, 那么暴力方法就可以判断到 n ^ 0.5 结束, 而不是到n – 1结束

C. 筛选法: 每次判断出一个质数p, 那么就把p * (p+1) … p * (p+2) … 直到n 的所有数字剔除, 这个方法可以找到小于等于n 的所有质数

D. 随机算法: Miller-Rabin 算法, 这个算法搜一下就有了, 但是这个算法不是确定的, 会有一定的概率找到一个数字不是质数, 但是判断出来是质数。

未完待续。

 

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on April 6, 2013