神奇的素数（一）——简谈素数

*素数在自然数中占有非常重要的地位，是一类既简单又神秘的数字，因其无规律性，在密码学中大量采用，所以有必要在这里单独列出讲一下

素数：

定义：素数又称为质数，是指在一个大于1的自然数中，除1和此整数本身外，无法被其他自然数整除的数，比1大但不是素数的数称为合数。

验证素数：其算法可分为两大类，即确定性算法及随机算法

确定性算法：

可以得出正确的结果，但通常算法较慢，如试除法:用需要验证的数N逐个除以从2开始值N-1中的所有数（后证实只需除到根号下N就行），若能被某一个数整除，表示N不是素数，反之则为素数。

//试除法函数
int is_prime(int n){

    int i;
    if(n <= 1){
        return 0;
    }

    for(i = 2;i * i <= n;i++){
        if(n % i== 0){
          return 0;　　　　}
    }
    return 1;
}

随机算法：与确定性算法相反，能较快速的得出结果但不一定准

寻找素数的算法：

此处我们采用著名的Eratosthenes求素数方法：如在2~100之间，我们先将所有2的倍数除去，再将所有3的倍数除去，然后是5，7的倍数除去就能得到100以内的所有素数，下面我们来编写一个程序求1000以内的素数

//用Eratosthenes求素数法，求1000以内的所有的素数#include<studio.h>#define MAXNUM 1000　　　　　　　　　　　　　　　　//求1000以内的所有素数int main(){　　int i,j,c = 0;　　int primr[MAXNUM + 1];　　　　　　　　　　　//定义保存素数的数组　　for(i = 2;i <= MAXNUM;i++){　　　　　　　　//初始化数组　　　　prime[i] = 1;　　　　　　　　　　　　　　//标志为1表示对应的数是素数　　}　　　　for(i = 2;i*i <= MAXNUM;i++){　　　　　　//循环处理前i个　　　　if(prime[i] == 1){　　　　　　　　　　　//若为素数，则进行筛选　　　　　　for(j = 2*i;j <= MAXNUM;j++){　　//筛去合数　　　　　　　　　　　　　　　　if(!prime[j]){　　　　　　　　　//是合数则跳过　　　　　　　　　　continue;　　　　　　　　}　　　　　　　　if(j%i = 0){　　　　　　　　　　//数j能被整除，说明不是素数　　　　　　　　　　primr[j] = 0;　　　　　　　//清除标志　　　　　　　　}　　　　　　}　　　　}　　}　　for(i = 2;i < MAXNUM;i++){　　　　　　　//输出素数　　　　if(prime[i] == 1){　　　　　　　　　　　　　　　　printf("%4d",i);　　　　　　　　　//是素数，则输出　　　　　　c++;　　　　　　if(c%10 == 0){　　　　　　　　　　//每行输出10个素数　　　　　　　　printf("\n");　　　　　　}　　　　}　　}　　printf("\n共有%d个素数！"，c)；　　getch();　　return 0;}

已被证明的素数定理：

1.在(a,2a]之间必有一个素数

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

2.存在任意长度的素数等差数列

3.其他已证明的素数定理

>一个偶数可以写成两个数字之和，其中每一个数字最多只有9个质因数

>一个偶数必定可以写成一个质数加上一个合数，其中的因子个数有上界

>一个偶数必定可以写成一个质数加上一个最多由5个因子所组成的合数，后来有人简称这个结果为（1+5）****

>一个充分大偶数必定可以写成一个素数加上一个最多有2个质因子所组成的合数，简称为（1+2）

原文链接: https://www.cnblogs.com/yimengxianzhi/p/7967494.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍