质数

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

质数详细介绍

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

质数简介

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。

质数的个数是无穷的。欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法：反证法。具体证明如下：假设质数只有有限的n个，从小到大依次排列为p₁，p₂，……，p_n，设N=p₁×p₂×……×p_n。如果

其他数学家给出了一些不同的证明。欧拉利用黎曼函数证明了全部素数的倒数之和是发散的，恩斯特·库默的证明更为简洁，哈里·弗斯滕伯格则用拓扑学加以证明。

尽管整个素数是无穷的，仍然有人会问“100，000以下有多少个素数？”，“一个随机的100位数多大可能是素数？”。素数定理可以回答此问题。

质数性质

1、质数p的约数只有两个：

1、和p。

2、算术基本定理：任一大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。

3、质数的个数是无限的。

4、质数的个数公式

5、若n为正整数，在

6、若n为大于或等于2的正整数，在n到

7、在一个大于1的数a和它的2倍之间（即区间（a, 2a]中）必存在至少一个素数。

8、存在任意长度的素数等差数列。

9、任一充分大的偶数都可以表示成一个素数加一个素因子个数不超过2个的数的和，简称为“1+2”。。

质数应用

质数被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入质数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中（实为寻找素数的过程），将会因为找质数的过程（分解质因数）过久，使即使取得信息也会无意义。

在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数设计成质数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。

在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的质数次数的使用也得到了证明。实验表明，质数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性。

以质数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。

多数生物的生命周期也是质数（单位为年），这样可以最大程度地减少碰见天敌的机会。

质数编程

质数基本判断思路

在一般领域，对正整数n，如果用2到

质数代码

Python 代码：

from math import sqrtdef 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.   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代码：

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#代码：

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代码：

#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("%dn",b);                }            }            i++;        }while(y != a);        x++;    }while(x <= 10000.0);//3到10000的素数    system("pause");//防止闪退    return 0;}

C/C++代码：

#include<iostream>#include<algorithm>#include<cmath>using namespace std;const long long size=100000;//修改size的数值以改变最终输出的大小long long zhishu;void work (){//主要程序    zhishu=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==0){                ok=!ok;                break;            }        }        if（ok）{            zhishu=i;            cout<<"count"<<k<<' '<<i<<endl;            k++;        }    }}int main（）{    freopen("zhishu.out","w",stdout);    cout<<"count1 2"<<endl;    work();    return 0;}

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代码：

function su(a:longint):boolean;varbegin    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代码：

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 ++) {        if (n % i == 0 || n % (i + 1) == 0) { return false; }    }    return true;}

Go代码：

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 代码

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 TrueEnd Function

ALGOL代码

begin    Boolean array a;    integer i,j;    for i := 2 step 1 until 100 do    a := true;    for i := 2 step 1 until 10 do        if a then                for j := 2 step 1 until 1000÷i do                    a := false;    for i := 2 step 1 until 100 do        if a then            print (i);end            

质数素性检测

素性检测一般用于数学或者加密学领域。用一定的算法来确定输入数是否是素数。不同于整数分解，素性测试一般不能得到输入数的素数因子，只说明输入数是否是素数。大整数的分解是一个计算难题，而素性测试是相对更为容易（其运行时间是输入数字大小的多项式关系）。有的素性测试证明输入数字是素数，而其他测试，比如米勒 - 拉宾（Miller–Rabin ）则是证明一个数字是合数。因此，后者可以称为合性测试。

素性测试通常是概率测试（不能给出100%正确结果）。这些测试使用除输入数之外，从一些样本空间随机出去的数；通常，随机素性测试绝不会把素数误判为合数，但它有可能为把一个合数误判为素数。误差的概率可通过多次重复试验几个独立值a而减小；对于两种常用的测试中，对任何合数n，至少一半的a检测n的合性，所以k的重复可以减小误差概率最多到

随机素性测试的基本结构：

1、随机选取一个数字a。

2、检测某个包含a和输入n的等式（与所使用的测试方法有关）。如果等式不成立，则n是合数，a作为n是合数的证据，测试完成。

3、从1步骤重复整个过程直到达到所设定的精确程度。

在几次或多次测试之后，如果n没有被判断为合数，那么可以说n可能是素数。

常见的检测算法：费马素性检验（Fermat primality test），米勒拉宾测试（Miller–Rabin primality test） ，Solovay–Strassen测试，卢卡斯-莱默检验法（Lucas–Lehmer primality test）。

质数筛素数法

筛素数法可以比枚举法节约极大量的时间（定n为所求最大值，m为≤n的质数个数，那么枚举需要O（n^2）的时间复杂度，而筛素数法为O（m*n）,显然m<<n，所以时间效率有很大提升。）。如1000000的数据范围，用筛素数法可在2s内解决。

思路：建立一个bool型数组M，若已知一个数M是质数，那么其i（i为正整数）倍M必然为合数，可将其去除。

//c++代码 all rights reserve.#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const long long size=1000000;//修改此值以改变要求到的最大值bool zhishu={false};int main（）{    freopen（"zhishu.out","w",stdout）;//输出答案至“筛质数（shaizhishu）.exe”所在文件夹内    zhishu=true;    for（long long i=3;i<=size;i+=2）zhishu=true;//所有奇数标为true，偶数为false    for（long long i=3;i<=size;i++）{        if（zhishu）{//如果i是质数            int cnt=2;            while（cnt*i<=size）{//把i的倍数标为false（因为它们是合数）                zhishu=false;                cnt++;            }        }    }    int cnt=1;    for（int i=2;i<=size;i++）{//全部遍历一遍        if（zhishu）{//如果仍然标记为true（是质数）则输出            cout<<cnt<<' '<<i<<endl;            cnt++;        }    }    return 0;}

筛选法的Java实现，如下：

public class SOE {    public static int calPrime（int n）{        if（n<=1）{            return 0;        }        byte origin = new byte;        int count = 0;        for（int i=2;i<n+1;i++）{            if（origin == 0）{                count++;                int k = 2;                while（i*k<=n）{                    origin = 1;                     k++;                }            }else{                continue;            }        }        return count;    }}

采用简单的埃氏筛选法和简单的开方判断素数法计算1000000以内素数的个数的效率比较：

StopWatch '计算1000000以内素数的个数': running time （millis） = 268

-----------------------------------------

ms % Task name

-----------------------------------------

00024 009% 简单的埃氏筛选法；

00244 091% 简单的开方判断素数法。

质数猜想

哥德巴赫猜想：是否每个大于2的偶数都可写成两个素数之和？

孪生素数猜想：孪生素数就是差为2的素数对，例如11和13。是否存在无穷多的孪生素数？

斐波那契数列内是否存在无穷多的素数？

是否有无穷多个的梅森素数？

在n与（n+1）之间是否每隔n就有一个素数？

是否存在无穷个形式如X+1素数？

黎曼猜想

质数哥德巴赫猜想

在1742年给欧拉的信中哥德巴赫提出了以下猜想：任一大于2的整数都可写成两个质数之和。因现今数学界已经不使用“1也是素数”这个约定，原初猜想的现代陈述为：任一大于5的整数都可写成三个质数之和。欧拉在回信中也提出另一等价版本，即任一大于2的偶数想陈述为欧拉的版本。

把命题"任一充分大的偶数都可以表示成为一个素因子个数不超过a个的数与另一个素因子不超过b个的数之和"记作"a+b"。1966年陈景润证明了"1+2"成立，即"任一充分大的偶数都可以表示成二个素数的和，或是一个素数和一个半素数的和"。　

今日常见的猜想陈述为欧拉的版本，即任一大于2的偶数都可写成两个素数之和，亦称为“强哥德巴赫猜想”或“关于偶数的哥德巴赫猜想”。

从关于偶数的哥德巴赫猜想，可推出任一大于7的奇数都可写成三个质数之和的猜想。后者称为“弱哥德巴赫猜想”或“关于奇数的哥德巴赫猜想”。

若关于偶数的哥德巴赫猜想是对的，则关于奇数的哥德巴赫猜想也会是对的。1937年时前苏联数学家维诺格拉多夫已经证明充分大的奇质数都能写成三个质数的和，也称为“哥德巴赫-维诺格拉朵夫定理”或“三素数定理”。2013年，秘鲁数学家哈拉尔德·赫尔弗戈特在巴黎高等师范学院宣称：证明了一个“弱哥德巴赫猜想”，即“任何一个大于7的奇数都能被表示成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”证明。

质数梅森质数

17世纪还有位法国数学家叫梅森，他曾经做过一个猜想：当2-1 中的p是质数时，2-1是质数。他验算出：当p=2、3、5、7、17、19时，所得代数式的值都是质数，后来，欧拉证明p=31时，2-1是质数。 p=2，3，5，7时，2-1都是素数，但p=11时，所得2,047=23×89却不是素数。

梅森去世250年后，美国数学家科尔证明，2-1=193,707,721×761,838,257,287，是一个合数。这是第九个梅森数。20世纪，人们先后证明：第10个梅森数是质数，第11个梅森数是合数。

由于这种质数珍奇而迷人，它被人们称为“数学珍宝”。值得一提的是，中国数学家和语言学家周海中根据已知的梅森质数及其排列，巧妙地运用联系观察法和不完全归纳法，于1992年正式提出了梅森素质分布的猜想，这一重要猜想被国际上称为“周氏猜测”。