文件名称:
Prime.md
所在目录:
Algorithm
文件大小:
1.61 KB
下载地址:
文本预览:
# 判定素数
素数：
## 直接判断
### 素数表
## 普通筛选法
基本思想：**素数的倍数一定不是素数**。用一个长度为N+1的数组保存信息（1 表示素数，0 表示非素数），先假设所有的数都是素数（初始化为1），从第一个素数2开始，把2的倍数都标记为非素数（置为0），一直到大于N；然后进行下一趟，找到2后面的下一个素数3，进行同样的处理，直到最后，数组中依然为0的数即为素数。
此筛选法的时间复杂度是O(nloglogn)，空间复杂度是O(n)。
不足之处也比较明显，手动模拟一遍就会发现，很多数被处理了不止1遍，比如6，在素数为2的时候处理1次，为3时候又标记一次，因此又造成了不必要处理。
## 线性筛素数
我们知道因式分解定理，任何一个非质（合）数都可以分解成质数的连乘积。
# 黑科技
我们知道可以使用正规表达式来做字符串匹配，但是竟然有人可以用正则表达式来判定素数！！！看下面的正则表达式
/^1?$|^(11+?)\1+$/
判定素数过程很简单，首先把自然数转成多个1的字符串，如：2 要写成 “11”， 3 要写成 “111”, 17 要写成“11111111111111111”，然后用上面的正则表达式来匹配，匹配成功则不是素数，否则是素数。
参考
[素数筛法的复杂度](http://zhiqiang.org/blog/science/computer-science/complexity-of-prime-sieve.html)
[检查素数的正则表达式](http://coolshell.cn/articles/2704.html)
[打印质数的各种算法](http://coolshell.cn/articles/3738.html)
素数：
## 直接判断
### 素数表
## 普通筛选法
基本思想：**素数的倍数一定不是素数**。用一个长度为N+1的数组保存信息（1 表示素数，0 表示非素数），先假设所有的数都是素数（初始化为1），从第一个素数2开始，把2的倍数都标记为非素数（置为0），一直到大于N；然后进行下一趟，找到2后面的下一个素数3，进行同样的处理，直到最后，数组中依然为0的数即为素数。
此筛选法的时间复杂度是O(nloglogn)，空间复杂度是O(n)。
不足之处也比较明显，手动模拟一遍就会发现，很多数被处理了不止1遍，比如6，在素数为2的时候处理1次，为3时候又标记一次，因此又造成了不必要处理。
## 线性筛素数
我们知道因式分解定理，任何一个非质（合）数都可以分解成质数的连乘积。
# 黑科技
我们知道可以使用正规表达式来做字符串匹配，但是竟然有人可以用正则表达式来判定素数！！！看下面的正则表达式
/^1?$|^(11+?)\1+$/
判定素数过程很简单，首先把自然数转成多个1的字符串，如：2 要写成 “11”， 3 要写成 “111”, 17 要写成“11111111111111111”，然后用上面的正则表达式来匹配，匹配成功则不是素数，否则是素数。
参考
[素数筛法的复杂度](http://zhiqiang.org/blog/science/computer-science/complexity-of-prime-sieve.html)
[检查素数的正则表达式](http://coolshell.cn/articles/2704.html)
[打印质数的各种算法](http://coolshell.cn/articles/3738.html)
git100:更名
点赞
回复
X