同义词 素数一般指质数质数（prime number）又称
素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他
因数的数称为质数。
中文名
质数
外文名
prime number
别 名
素数
例 子
2、3、5、7、11、13、17、19
讨论范围
非0自然数
拼 音
zhi shu
定 义
只有1和它本身两个因数的自然数
反义词
合数
目录
1
定义个数2
猜想3
性质编程基本判断思路：Python 代码：Java代码：Php代码：C#代码：C代码：C/C++代码：Pascal代码：Javascript代码：Go代码：Basic 代码ALGOL代码素性检测筛素数法4
难题哥德巴赫猜想黎曼猜想孪生质数梅森质数5
素数的密度公式素数及伪素数通项公式素数的变量n的通项公式应用量级定义
质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数
个数
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
质数的个数是无穷的。
欧几里得的《
几何原本》中有一个经典的证明。它使用了证明常用的方法：
反证法。具体证明如下：假设质数只有有限的n个，从小到大依次排列为p1，p2，……，pn，设N=p1×p2×……×pn，那么，pn加一是素数或者不是素数。
如果pn加一为素数，则pn加一要大于p1，p2，……，pn，所以它不在那些假设的素数集合中。
如果pn加一为
合数，因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1，所以pn加一不可能被p1，p2，……，pn整除，所以该合数分解得到的素因数肯定不在假设的素数
集合中。
因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立。也就是说，素数有无穷多个。
其他数学家给出了一些不同的证明。欧拉利用
黎曼函数证明了全部素数的倒数之和是发散的，恩斯特·库默的证明更为简洁，
哈里·弗斯滕伯格则用
拓扑学加以证明。
素数两性定理
6（x）+-1=（pP）6乘以完全不等数加减1是一对孪生素数。
其中，6（X-1=（P 6乘以阴性不等数减去1等于阴性素数；
6X）+1=P）6乘以阳性不等数加上1等于阳性素数。
（X=/=6NM+-（M-N）阴性不等数不等于阴性上下两式；
X）=/=6NM+-（N+M）阳性不等数不等于阳性上下两式。
（x)=/=6NM+-(M+-N) 完全不等数不等于阴阳上下四式产生的数。
（N，M两个自然数，N=《M）
素数分布规律
以36N（N+1）为单位，随着N的增大，素数的个数以波浪
形式渐渐增多。
孪生质数也有相同的分布规律。
以下15个区间内质数和孪生质数的统计数。
S1区间1——72，有素数18个，孪生素数7对。（2和3不计算在内，最后的数是孪中的也算在前面区间。）
S2区间73——216，有素数27个，孪生素数7对。
S3区间217——432，有素数36个，孪生素数8对。
S4区间433——720，有素数45个，孪生素数7对。
S5区间721——1080，有素数52个，孪生素数8对。
S6区间1081——1512，素数60个，孪生素数9对。
S7区间1513——2016，素数65个，孪生素数11对。
S8区间2017——2592，素数72个，孪生素数12对。
S9区间2593——3240，素数80个，孪生素数10对。
S10区间3241——3960，素数91个，孪生素数18对。
S11区间3961——4752素数92个，孪生素数17对。
S12区间4752——5616素数98个，孪生素数13对。
S13区间5617——6552素数108个，孪生素数14对。
S14区间6553——7560素数113个，孪生素数19对。
S15区间7561——8640素数116个，孪生素数14对。（以上没有校正，可能有误差。）
素数分布规律的发现，许多素数问题可以解决。
对于一定范围内的素数数目的计算
尽管整个素数是无穷的，仍然有人会问“100，000以下有多少个素数？”，“一个随机的100位数多大可能是素数？”。
素数定理可以回答此问题。
在一个大于1的数a和它的2倍之间（即区间(a, 2a]中）必存在至少一个素数。
存在任意长度的素数等差数列。（格林和
陶哲轩，2004年[1] ）
一个偶数可以写成两个合数之和，其中每一个合数都最多只有9个质因数。（
挪威数学家布朗，1920年）
一个偶数必定可以写成一个质数加上一个合成数，其中合数的因子个数有上界。（瑞尼，1948年）
一个偶数必定可以写成一个质数加上一个最多由5个因子所组成的合成数。后来，有人简称这结果为 (1 + 5)(中国
潘承洞，1968年)
一个充分大偶数必定可以写成一个素数加上一个最多由2个质因子所组成的合成数。简称为 (1 + 2)(中国
陈景润)[2]
猜想
哥德巴赫猜想：是否每个大于2的偶数都可写成两个素数之和？
孪生素数猜想：孪生素数就是差为2的素数对，例如11和13。是否存在无穷多的孪生素数？
斐波那契数列内是否存在无穷多的素数？
是否有无穷多个的
梅森素数？
在n2与（n+1）2之间是否每隔n就有一个素数？
是否存在无穷个形式如X2+1素数？
黎曼猜想孪生素数是无限多的证明
关键词:完全不等数,SN区间,LN区间.
一。素数两性定理
大于3的素数只分布在6n-1和6n+1两数列中。（n非0自然数，下同）
6n-1数列中的合数叫阴性合数，其中的素数叫阴性素数；6n+1数列中的合数叫阳性合数，其中的素数叫阳性素数。
阴性合数定理
6[6NM+（M-N）]-1=（6N+1）（6M-1）（N M两个非0自然数，N=〈 M，下同）
6[6NM-（M-N）]-1=（6N-1）（6M+1）
在6n-1数列中只有这两种合数，余下就是阴性素数了，所以就有阴性素数定理
6NM+-（M-N）=/=x（阴性不等数）
6x-1=q（阴性素数）
阳性合数定理
6[6NM+（N+M）]+1=（6N+1）（6M+1）
6[6NM-（N+M）]+1=（6N-1）（6M-1）
在6n+1数列中只有这两种合数，余下就是阳性素数了，所以就有阳性素数定理
6NM+-（N+M）=/=X（阳性不等数）
6X+1=P（阳性素数）
二。与孪生素数相对应的完全不等数
完全不等数(X),它既不等于阴性上下两式；也不等于阳性上下两式。
(X)=/=6NM+-(M+-N)
则有6(X)+1=P 6(X)-1=q （p减1能被6整除的素数，q加1能被6整除的素数，下同）
一个完全不等数所产生的阴性素数q和阳性素数P就是一对孪生素数.
并且完全不等数与孪生素数是一一对应的.
三。阴阳四种等数在自然数列中的分布概况
6NM+（M-N）=阴性上等数6NM-（M-N）=阴性下等数
6NM+（N+M）=阳性上等数6NM-（N+M）=阳性下等数
为了搞清它们在自然数中分布情况，把四式中的N叫级别因子数，M叫无限因子数。
四种等数的每一个级别的最小等数都在6NN+-（N+N）范围。
每一级别的上等数相邻两等数距离是6n+1，在自然数列中比例是1/（6n+1），两种上等数每个级别的比例合计是2/（6n+1），（但实际是略少于这个比例因每一级别的底部都没有这个级别的上等数；下等数也一样的情况。）
每一级别的下等数相邻等数的距离是6n-1，在自然数列中的比例是1/（6n-1），阴阳两种下等数的每个级别的合计比例是2/（6n-1）。
每个级别的四种等数在自然数列中的比例是24N/[(6N+1)(6N-1)].
四。四种等数大小数列的互相渗透
自然数列中有阴性上等数数列，阴性的下等数数列，阳性上等数数列和阳性下等数数列。它们的级别有无限多，每一个级别的数列的等数都是无限多的。同一种等数级别不同的数列都是互相渗透而产生重叠，并以两级别的等数距离的乘积而严格地重叠的。在计算一种若干的级别的等数时用连乘式正好可以表示它的渗透重叠关系。四种等数数列之间都有互相渗透而重叠，只有同一级别阴阳上上数列.下下数列没有渗透.四种数列之间的渗透重叠不用计算也足够可以证明了。
五。与素数分布基本同步的SN区间
把自然数划分成12，24，36……以12为递增的一个个区间，这样的区间叫SN区间。SN区间与四种等数数列是同步的，即:
12（1+2+3+……+N）=6NN+6N
在这样的区间内包括N级别及以下的所有四种等数数列的等数，并没有比N级别大的数列等数，与四种等数的级别是完全同步的，所以与素数的分布也是同步的。
六。每个大于S8区间内都有8个以上的完全不等数
在每一个SN区间只有存在1至N级别的四种数列等数，每一级别等数的比例是可以确定，由于上下级别的渗透。就可以拿以下式来计算S8区间的完全不等数的至少个数。
12*8*11/35*95/143*251/323*479/575*779/899*1151/1295*1593/1763*2111/2303=8.2768
其他每一个SN区间可用这种方法计算.
随着区间的增大完全不等数计算的数量也会越来越多.以后都会超过8个.
七。误差分析
用最严格下取整的误差分析方法，将SN区间捆绑成1,2,4,8,16......2^(N-1)的LN区间.在每一个大于S8的SN区间计算都大于8个完全不等数,在每一个LN区间都有2^N-1级别等数数列, 每级级别有4种等数数列,每一级别一种等数筛一次误差极限是1 .每一个LN区间误差极限是4*(2^N-1).
8*2^(N-1)-4*(2^N-1)=4
最严格下取整后大于L4的区间仍然还有4个完全不等数。
八。总结
根据以上的论证，在大于S8区间每一个SN区间都有8个以上的完全不等数.
严格的下取整后，大于L4的每一个LN区间都还有多于4个的完全不等数以上的量。
LN区间是无限多的，完全不等数与孪生素数对是一一对应的，所以孪生素数也是无限多的。
这个证明期待着权威的表态。
性质
质数具有许多独特的性质：
（1）质数p的约数只有两个：1和p。
（2）初等数学基本定理：任一大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。
（3）质数的个数是
无限的。
（4）质数的个数公式
是不减函数。
（5）若n为
正整数，在
到
之间至少有一个质数。
（6）若n为大于或等于2的正整数，在n到
之间至少有一个质数。
（7）若质数p为不超过n(
)的最大质数，则
。
（8）所有大于10的质数中，个位数只有1,3,7，9。
编程
基本判断思路：
在一般领域，对正整数n，如果用2到
之间的所有整数去除，均无法整除，则n为质数。
质数大于等于2 不能被它本身和1以外的数整除
Python 代码：
1
2
3
4
5
6
7
8
from math import sqrt
def is_prime(n):
if n == 1:
return False
for i in range(2, int(sqrt(n))+1):
if n % i == 0:
return False
return True
Java代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
1.
public static boolean testIsPrime2(int n){
if (n <= 3) {
return n > 1;
}
for(int i=2;i<n;i++){
if(n%i == 0)
return false;
}
return true;
}
/*优化后*/
public static boolean testIsPrime3(int n){
if (n <= 3) {
return n > 1;
}
for(int i=2;i<=Math.sqrt(n);i++){
if(n%i == 0)
return false;
}
return true;
}
2.
public class Prime {
public static void main(String[] args) {
int a = 17; //判断17是不是质数
int c = 0;
for (int b = 2; b < a; b++) {
if (a % b != 0) {
c++;
}
}
if (c == a - 2) {
System.out.println(a + "是质数");
} else {
System.out.println(a + "不是质数");
}
}
}
Php代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function isPrime($n) {//TurkHackTeam AVP production
if ($n <= 3) {
return $n > 1;
} else if ($n % 2 === 0 || $n % 3 === 0) {
return false;
} else {
for ($i = 5; $i * $i <= $n; $i += 6) {
if ($n % $i === 0 || $n % ($i + 2) === 0) {
return false;
}
}
return true;
}
}
C#代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
using System;
namespace 计算质数
{
class Program
{
static void Main(string[] args)
{
for (int i = 2,j=1; i < 2100000000&&j<=1000; i++)//输出21亿内的所有质数，j控制只输出1000个。
{
if (st(i))
{
Console.WriteLine("{0,-10}{1}",j,i);
j++;
}
}
}
static bool st(int n)//判断一个数n是否为质数
{
int m = (int)Math.Sqrt(n);
for(int i=2;i<=m;i++)
{
if(n%i==0 && i!=n)
return false;
}
return true;
}
}
}
C代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
#include <windows.h>
int main()
{
double x,y,i;
int a,b;
x = 3.0;
do{
i = 2.0;
do{
y = x / i;
a = (int)y;
if(y != a)//用于判断是否为整数
{
if(i == x - 1)
{
b = (int)x;
printf("%d\n",b);
}
}
i++;
}while(y != a);
x++;
}while(x <= 10000.0);//3到10000的素数
system("pause");//防止闪退
return 0;
}
C/C++代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const long long size=100000;//修改size的数值以改变最终输出的大小
long long zhishu[size/2];
void work(){//主要程序
zhishu[1]=2;
long long k=2;
for(long long i=3;i<=size;i++){//枚举每个数
bool ok=1;
for(long long j=1;j<k;j++){//枚举已经得到的质数
if(i%zhishu[j]==0){
ok=!ok;
break;
}
}
if(ok){
zhishu[k]=i;
cout<<"count"<<k<<' '<<i<<endl;
k++;
}
}
}
int main(){
freopen("zhishu.out","w",stdout);
cout<<"count1 2"<<endl;
work();
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isPrime(unsigned long n) {
if (n <= 3) {
return n > 1;
} else if (n % 2 == 0 || n % 3 == 0) {
return false;
} else {
for (unsigned short i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
}
Pascal代码：
1
2
3
4
5
6
function su(a:longint):boolean;
var
begin
if a=2 then exit(true) else for i:=2 to trunc(sqrt(a))+1 do if a mod i=0 then exit(false);
exit(true);
end.
Javascript代码：
1
2
3
4
5
6
7
8
9
function isPrime(n) {
if (n <= 3) { return n > 1; }
if (n % 2 == 0 || n % 3 == 0) { return false; }
for (var i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) { return false; }
}
return true;
}
Go代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func isPrime(value int) bool {
if value <= 3 {
return value >= 2
}
if value%2 == 0 || value%3 == 0 {
return false
}
for i := 5; i*i <= value; i += 6 {
if value%i == 0 || value%(i+2) == 0 {
return false
}
}
return true
}
Basic 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Private Function IfPrime(ByVal x As Long) As Boolean
Dim i As Long
If x < 0 Then x = -x
If x = 2 Then Return True
If x = 1 Then Return True
If x = 3 Then Return False
If x = 0 Then
MsgBox("error",,)
Return False
End If
For i = 2 To Int(Sqrt(x)) Step 1
If x Mod i = 0 Then Return False
Next i
Return True
End Function
ALGOL代码
1
2
3
4
5
6
7
8
9
10
11
12
13
begin
Boolean array a[2:100];
integer i,j;
for i := 2 step 1 until 100 do
a[i] := true;
for i := 2 step 1 until 10 do
if a[i] then
for j := 2 step 1 until 1000÷i do
a[i × j] := false;
for i := 2 step 1 until 100 do
if a[i] then
print (i);
end
素性检测
上下素性判决定法
首先，本文英文字母都表示整数，上半部B 》3N 》W，下半部B 》W 》3N。大于3的素数只有6N-1和6N+1两种形式，我们只需判定这两种数是素数还是合数即可。
命题 1 对于B=36N+1 形数而言。
若不定方程（3N）^2+N-（B-1）/36=W^2 有整数解，
则 6（3N-W）+1 是小因子数；6（3N+W）+1 是大因子数。
若不定方程 （3N）^2-N-（B-1）/36=W^2 有整数解，
则 6（3N-W）-1 是小因子数；6（3N+W）-1 是大因子数。
两式都无解，是素数。
命题 2对于B=36N+7 形数而言。
若不定方 （3N）^2+4N-（B-7）/36=W^2+W 有整数解，
则 6（3N-W）+1 是小因子数，6（3N+W+1）+1 是大因子数。
若不定方程 （3N+2）^2+2N+2-（B+29）/36=W^2+W 有整数解，
则 6（3N+2-W）-1 是小因子数，6（3N+W+3）-1 是大因子数。
两式都无解，是素数。
命题 3对于B=36N+13 形数而言。
若不定方程 （3N+1）^2+N-（B-13）/36=W^2 有整数解，
则 6（3N+1-W）+1 是小因子数，6（3N+1+W）+1是大因子数。
若不定方程 （3N+2）^2-N-（B+23）/36=W2 有整数解，
则 6（3N+2-W）-1 是小因子数，6（3N+2+W）-1是大因子数。
两式都无解，是素数。
命题 4 对于B=36N+19 形数而言。
若不定方程（3N+1）^2+4N+1-（B-19）/36=W^2 +W 有整数解，
则 6（3N+1-W）+1 是小因子数；6（3N+2+W）+1 是大因子数。
若不定方程 （3N+1）^2+2N+1-（B+17）/36=W^2 +W 有整数解，
则 6（3N+1-W）-1 是小因子数；6（3N+2+W）-1 是大因子数。
两式都无解，是素数。
命题 5 对于B=36N+25 形数而言。
若不定方 （3N+2）^2+N-（B-25）/36=W^2有整数解，
则 6（3N+2-W）+1 是小因子数，6（3N+2+W）+1 是大因子数。
若不定方程 （3N+1）^2-N-（B+11）/36=W^2有整数解，
则 6（3N+1-W）-1 是小因子数，6（3N+1+W）-1 是大因子数。
两式都无解，是素数。
命题 6 对于B=36N+31 形数而言。
若不定方程 （3N+2）^2+4N+2-（B-31）/36=W^2 +W 有整数解，
则 6（3N+2-W）+1 是小因子数，6（3N+3+W）+1是大因子数。
若不定方程 （3N+1）^2-4N-1-（B+5）/36=W^2+W有整数解，
则 6（3N-W）-1 是小因子数，6（3N+1+W）-1是大因子数。
两式都无解，是素数。
命题 7对于B=36N-1 形数而言。
若不定方程（3N）^2-N+（B-1）/36=W^2 有整数解，
则 6（3N-W）+1 是小因子数；6（3N+W）-1 是大因子数。
若不定方程 （3N）^2+N+（B-1）/36=W^2 有整数解，
则 6（W-3N）-1 是小因子数；6（W+3N）+1 是大因子数。
两式都无解，是素数。
命题 8对于B=36N+5 形数而言。
若不定方 （3N）^2+2N+（B-5）/36=W^2+W 有整数解，
则 6（W-3N）+1 是小因子数，6（W+3N+1）-1 是大因子数。
若不定方程 （3N+2）^2+4N+2+（B+31）/36=W^2+W 有整数解，
则 6（W-3N-2）-1 是小因子数，6（W+3N+3）+1 是大因子数。
两式都无解，是素数。
命题 9对于B=36N+11 形数而言。
若不定方程 （3N+1）^2-N+（B-11）/36=W^2 有整数解，
则 6（W-3N-1）+1 是小因子数，6（W+3N+1）-1是大因子数。
若不定方程 （3N+2）^2+N+(B+25）/36=W2 有整数解，
则 6(W-3N-2）-1 是小因子数，6（W+3N+2）+1是大因子数。
两式都无解，是素数。
命题 10 对于B=36N+17 形数而言。
若不定方程（3N+1）^2+2N+1+（B-17）/36=W^2 +W 有整数解，
则 6（W-3N-1）+1 是小因子数；6（W+3N+2）-1 是大因子数。
若不定方程 （3N+1）^2+4N+1+（B+19）/36=W^2 +W 有整数解，
则 6（W-3N-1）-1 是小因子数；6（W+3N+2）+1 是大因子数。
两式都无解，是素数。
命题 11 对于B=36N+23 形数而言。
若不定方 （3N+2）^2-N+（B-23）/36=W^2有整数解，
则 6（W-3N-2）+1 是小因子数，6（W+3N+2）+1 是大因子数。
若不定方程 （3N+1）^2+N+（B+13）/36=W^2有整数解，
则 6（W-3N-1）-1 是小因子数，6（W+3N+1）+1 是大因子数。
两式都无解，是素数。
命题 12 对于B=36N+31 形数而言。
若不定方程 （3N+2）^2+2N+2+（B-29）/36=W^2 +W 有整数解，
则 6（W-3N-2）+1 是小因子数，6（W+3N+3）-1是大因子数。
若不定方程 （3N）^2-4N+（B+7）/36=W^2+W有整数解，
则 6（W-3N）-1 是小因子数，6（W+3N+1）+1是大因子数。
两式都无解，是素数。
素性检测一般用于数学或者加密学领域。用一定的算法来确定输入数是否是素数。不同于整数分解，素性测试一般不能得到输入数的素数因子，只说明输入数是否是素数。大整数的分解是一个计算难题，而素性测试是相对更为容易（其运行时间是输入数字大小的多项式关系）。有的素性测试证明输入数字是素数，而其他测试，比如米勒 - 拉宾（Miller–Rabin ）则是证明一个数字是合数。因此，后者可以称为合性测试。
素性测试通常是概率测试（不能给出100%正确结果）。这些测试使用除输入数之外，从一些样本空间随机出去的数；通常，随机素性测试绝不会把素数误判为合数，但它有可能为把一个合数误判为素数。误差的概率可通过多次重复试验几个独立值a而减小；对于两种常用的测试中，对任何合数n，至少一半的a检测n的合性，所以k的重复可以减小误差概率最多到2^{-k}，可以通过增加k来使得误差尽量小。
随机素性测试的基本结构：
1.随机选取一个数字a。
2.检测某个包含a和输入n的等式（与所使用的测试方法有关）。如果等式不成立，则n是合数，a作为n是合数的证据，测试完成。
3.从1步骤重复整个过程直到达到所设定的精确程度。
在几次或多次测试之后，如果n没有被判断为合数，那么我们可以说n可能是素数。
常见的检测算法：
费马素性检验（Fermat primality test），米勒拉宾测试（Miller–Rabin primality test） ，Solovay–Strassen测试（Solovay–Strassen primality test），
卢卡斯-莱默检验法（英语：Lucas–Lehmer primality test）。
筛素数法
筛素数法可以比枚举法节约极大量的时间（定n为所求最大值，m为<=n的质数个数，那么枚举需要O(n^2)的时间复杂度，而筛素数法为O(m*n),显然m<<n，所以时间效率有很大提升。）。如1000000的数据范围，用筛素数法可在2s内解决，
思路：建立一个bool型数组M，若已知一个数M[k]是质数，那么其i（i为正整数）倍M[k*i]必然为合数，可将其去除。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//c++代码 all rights reserve.
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const long long size=1000000;//修改此值以改变要求到的最大值
bool zhishu[size+5]={false};
int main(){
freopen("zhishu.out","w",stdout);//输出答案至“筛质数（shaizhishu）.exe”所在文件夹内
zhishu[2]=true;
for(long long i=3;i<=size;i+=2)zhishu[i]=true;//所有奇数标为true，偶数为false
for(long long i=3;i<=size;i++){
if(zhishu[i]){//如果i是质数
int cnt=2;
while(cnt*i<=size){//把i的倍数标为false（因为它们是合数）
zhishu[cnt*i]=false;
cnt++;
}
}
}
int cnt=1;
for(int i=2;i<=size;i++){//全部遍历一遍
if(zhishu[i]){//如果仍然标记为true（是质数）则输出
cout<<cnt<<' '<<i<<endl;
cnt++;
}
}
return 0;
}
/*
样例输出结果，第一个数是个数，第二个是第几个质数
1 2
2 3
3 5
4 7
5 11
6 13
7 17
8 19
9 23
10 29
11 31
12 37
13 41
14 43
15 47
16 53
17 59
18 61
19 67
20 71
21 73
22 79
23 83
24 89
25 97
*/
筛选法的Java实现，如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* @title SOE
* @desc 简单的埃氏筛选法计算素数
* @author he11o
* @date 2016年5月3日
* @version 1.0
*/
public class SOE {
public static int calPrime(int n){
if(n<=1){
return 0;
}
byte[] origin = new byte[n+1];
int count = 0;
for(int i=2;i<n+1;i++){
if(origin[i] == 0){
count++;
int k = 2;
while(i*k<=n){
origin[i*k] = 1;
k++;
}
}else{
continue;
}
}
return count;
}
}
采用简单的埃氏筛选法和简单的开方判断素数法计算1000000以内素数的个数的效率比较：
StopWatch '计算1000000以内素数的个数': running time (millis) = 268
-----------------------------------------
ms % Task name
-----------------------------------------
00024 009% 简单的埃氏筛选法
00244 091% 简单的开方判断素数法
难题
哥德巴赫猜想
哥德巴赫猜想证明的困难在于，任何能找到的素数，在以下式中都是不成立的。2*3*5*7*。。。。。。*PN*P=PN+（2*3*5*7*。。。。。。*P-1）*PN前面的偶数减去任何一个素数PN的差必是合数.
在1742年给
欧拉的信中
哥德巴赫提出了以下猜想：任一大于2的
整数都可写成两个质数之和。因现今数学界已经不使用“1也是素数”这个约定，原初猜想的现代陈述为：任一大于5的整数都可写成三个质数之和。欧拉在回信中也提出另一
等价版本，即任一大于2的偶数想陈述为欧拉的版本。把命题"任一充分大的
偶数都可以表示成为一个素因子个数不超过a个的数与另一个素因子不超过b个的数之和"记作"a+b"。1966年
陈景润证明了"1+2"成立，即"任一充分大的偶数都可以表示成二个素数的和，或是一个素数和一个
半素数的和"。 今日常见的猜想陈述为欧拉的版本，即任一大于2的偶数都可写成两个素数之和，亦称为“强哥德巴赫猜想”或“关于偶数的哥德巴赫猜想”。
从关于偶数的
哥德巴赫猜想，可推出任一大于7的奇数都可写成三个质数之和的猜想。后者称为“
弱哥德巴赫猜想”或“关于
奇数的哥德巴赫猜想”。
若关于偶数的
哥德巴赫猜想是对的，则关于奇数的哥德巴赫猜想也会是对的。1937年时
前苏联数学家
维诺格拉多夫已经证明充分大的奇质数都能写成三个质数的和，也称为“哥德巴赫-维诺格拉朵夫定理”或“三素数定理”。2013年，
秘鲁数学家哈拉尔德·赫尔弗戈特在巴黎高等师范学院宣称：证明了一个“弱哥德巴赫猜想”，即“任何一个大于7的奇数都能被表示成3个奇素数之和”。[3]
黎曼猜想
黎曼猜想是关于黎曼ζ函数ζ(s)的零点分布的猜想，由数学家
波恩哈德·黎曼（1826～1866）于1859年提出。德国数学家希尔伯特列出23个数学问题。其中第8问题中便有
黎曼假设。素数在自然数中的分布并没有简单的规律。黎曼发现素数出现的频率与黎曼ζ函数紧密相关。黎曼猜想提出：黎曼ζ函数ζ(s)非平凡零点（在此情况下是指s不为-2、-4、-6等点的值）的
实数部份是1/2。即所有非平凡零点都应该位于直线1/2 + ti（“
临界线”（critical line））上。t为一实数，而i为
虚数的基本单位。至今尚无人给出一个令人信服的关于黎曼猜想的合理证明。
在黎曼猜想的研究中，数学家们把复平面上 Re(s)=1/2 的直线称为 critical line。 运用这一术语，
黎曼猜想也可以表述为：黎曼ζ 函数的所有非平凡零点都位于 critical line 上。
黎曼猜想是黎曼在 1859 年提出的。在证明
素数定理的过程中，黎曼提出了一个论断：Zeta函数的零点都在直线Res(s) = 1/2上。他在作了一番努力而未能证明后便放弃了，因为这对他证明素数定理影响不大。但这一问题至今仍然未能解决，甚至于比此假设简单的猜想也未能获证。而函数论和
解析数论中的很多问题都依赖于
黎曼假设。在
代数数论中的广义黎曼假设更是影响深远。若能证明黎曼假设，则可带动许多问题的解决。
孪生质数
1849年，
波林那克提出
孪生质数猜想（the conjecture of twin primes），即猜测存在无穷多对孪生质数。猜想中的“
孪生质数”是指一对质数，它们之间相差2。例如3和5，5和7，11和13，10,016,957和10,016,959等等都是孪生质数。
英国数学家戈弗雷·哈代和约翰·李特尔伍德曾提出一个“强
孪生素数猜想”。这一猜想不仅提出孪生素数有无穷多对，而且还给出其渐近分布形式。2013年5月14日，《自然》(Nature)杂志在线报道张益唐证明了“存在无穷多个之差小于7000万的素数对”，这一研究随即被认为在孪生素数猜想这一终极数论问题上取得了重大突破，甚至有人认为其对学界的影响将超过陈景润的“1+2”证明。[4]
36N（N+1）+ -1形的孪生素数，N《100000000 有109128对。
梅森质数
17世纪还有位法国数学家叫
梅森，他曾经做过一个猜想：当2p-1 中的p是质数时，2p-1是质数。他验算出：当p=2、3、5、7、17、19时，所得代数式的值都是质数，后来，欧拉证明p=31时，2p-1是质数。 p=2，3，5，7时，2p-1都是素数，但p=11时，所得2,047=23×89却不是素数。
梅森去世250年后，美国数学家
科尔证明，267-1=193,707,721×761,838,257,287，是一个合数。这是第九个梅森数。20世纪，人们先后证明：第10个梅森数是质数，第11个梅森数是合数。质数排列得杂乱无章，也给人们寻找质数规律造成了困难。
迄今为止，人类仅发现49个梅森质数。美国中央密苏里大学于2016年1月7日发现的质数，为迄今发现的最大质数，同时是一个梅森质数。由于这种质数珍奇而迷人，它被人们称为“数学珍宝”。值得一提的是，中国数学家和语言学家
周海中根据已知的梅森质数及其排列，巧妙地运用联系观察法和不完全归纳法，于1992年正式提出了梅森素质分布的猜想，这一重要猜想被国际上称为“
周氏猜测”。[3]
(
GIMPS)项目于2016年1月7日找到了目前人类已知的最大素数274,207,281-1，该素数有22,338,618位，是第49个梅森素数。
素数的密度公式
根据
构造函数
a为常数 且
1-1
根据1-1 性质 以多项式
为函数
中的指数
得
1-2
当 n 为素数或 1 时，
等于 1，当 n 为合数时，
等于 0
得素数密度公式
式中 1 定义为素数
素数及伪素数通项公式
把它拓展到实数那么它的切线为:
由切线方程知，素数永远在斜率3的折线上摆动，最大斜率3+
，最小斜率3-
。
素数的变量n的通项公式
有以上公式能够确定伪素数及素数，那么通过对其变量n的识别，我们可以写出任意素数或伪素数
先确定伪素数的变量n,用n(x,y)来表示它，变量是个三维变量，公式如下：
n为偶数时：x,y 均自然数
n为奇数时：
满足以上条件时是P(n)为素数。excel vba 素数输出程序详见
素数公式词条。
应用量级
质数被利用在
密码学上，所谓的
公钥就是将想要传递的信息在编码时加入质数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的
密钥，则解密的过程中（实为寻找素数的过程），将会因为找质数的过程（
分解质因数）过久，使即使取得信息也会无意义。
在汽车
变速箱齿轮的设计上，相邻的两个大小齿轮齿数最好设计成质数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。
在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的质数次数的使用也得到了证明。实验表明，质数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性。
以质数形式无规律变化的导弹和
鱼雷可以使敌人不易拦截。
多数生物的生命周期也是质数（单位为年），这样可以最大程度地减少碰见天敌的机会。
参考资料
1.
Green, B. and Tao, T.．The primes contain arbitrarily long and arithmetic progression：Annals of Mathematics ，2005-09-12
2.
陈景润．大偶数表为一个素数及一个不超过二个素数的乘积之和：中国科学A辑，1973, (2)：111–128
3.
数学猜想：推动科学发展的强大动力之一 ．光明网．2013-06-17
4.
华人破译孪生素数猜想 影响或超陈景润1+2证明 ．人民网
词条标签：
非科学
