C语言的素数的全家桶

整理了素数的判断筛选的一些方法，建议留出时间肝一下。

首先由简入难，思考一下如何判断一个数是不是素数？

最简单最暴力的方法就是定义法了，即根据素数的定义（除1以外的数，只能被1和它本身整除），通过循环，判断2到这个数之间有没有可以被这个数整除的数，有就不是素数，没有就是素数。

理解简单代码也简单：

#include
int ssf1(int n)//判断n是否为素数，是返回1，不是返回0
{
    int j;
    for(j=2;j 
优化1： 
那么把这个简单暴力的方法优化一下，优化前首先要了解一个事情，就是对于任何一个正整数n，都可以写成√(n-x）*√(n-x)的形式，ok，我们在上面那个方法中判断n是否是素数时，是将2到n-1之间的整数每一个都要判断一遍，直到中途结束或最终结束，现在我们就只需要判断2到√n之间的整数就可以，为什么？首先为什么不判断√n以后的数了，因为因为如果2到√n之间有一个整数数能被n整除，n就不是素数，而如果2到√n之间没有一个整数能被n整除，那么√n之后的也不会被n整除，思考一下。
 
理解好了，代码也就出来了：
 
#include
int ssf2(int n)//是素数返回1，不是返回0
{
    int j;
    for(j=2;j*j<=n;j++)
        if(n%j==0)
        return 0;
    return 1;
}
int main()
{
    int n;
    scanf("%d",&n);
    if(ssf2(n))
       printf("YESn");
    else
       printf("NOn");
    return 0;
}
 
优化2： 
ok，这样已经好多了，但是还可以再优化优化，也是优化前先了解个事情，那就是除了2和3以外的素数，其他的素数一定位于6的倍数两侧，但位于6的倍数两侧的数不一定是素数。
 
 
 
需要看证明的看一下，不需要的就可以想一下如何优化代码了：                                               设 x>=1,可以把6个相连整数表示为6x-1,6x,6x+1,6x+2,6x+3,6x+4,6x+5的形式，不是6倍数两侧的数有：6x,6x+2,6x+3,6x+4。到这里聪明的小孩子已经开始点头了。
 
 
那么怎么优化，首先直接规定好两个特殊的2和3，然后不是6的倍数两侧的数直接干掉，是6两侧的数再去用上面那个方法判断，但是这里我们也可以做一个优化，让2到√n之间的整数判断改为5到√n之间的间隔数，每次间隔为6,因为：
 
 
 
前面排除了6x，6x+2，6x+3,6x+4，只剩下6x+5和6x-1的数，所以n可以表示为6x+5或6x-1的形式，那么n就是奇数，而对于n要整除的数可以表示为：
 
 
6i-1,6x,6i+1,6i+2,6i+3,6i+4,6i+5的形式（i>=5），对于6i+2,6i+4,6i都是偶数，n是奇数，不可能整除一个偶数，所以这种形式的数就不需要判断了，而对于6i+3,如果能被n整除，那么n一也能整除3，但n是6x+5或6x-1，不能整除3，所以6i+3,不能被n整除，也就不用判断6i+3形式的数了，所以只需要判断6i-1和6i+5形式的数能否被n整除就可以了。
 
 
理解了，代码也就出来了：
 
#include
int ssf3(int n)
{
    if(n==2||n==3)
        return 1;
    if(n%6!=5&&n%6!=1)
        return 0;
    int i;
    for(i=5;i*i<=n;i++)
        if(n%i==0||n%(n+2)==0)
        return 0;
    return 1;
}
int main()
{
    int n;
    scanf("%d",&n);
    if(ssf3(n))
       printf("YESn");
    else
       printf("NOn");
    return 0;
}
 
ok，简单的完事，整点不算简单的，可曾听闻过埃氏筛和欧拉筛？用来求区间内的素数的。
 
思考一下，求[1,n]内所有的素数怎么搞？从[2,n]的每一个数用上面的三个方法吗？
 
要判断好好好好好好好多次， 那么就来整下埃氏筛和欧拉筛吧。
 
欧拉筛 
原理很简单：
 
（1）就是将素数的乘以2以上的倍数踢出去（这个过程随便成为倍数筛除吧），剩下的就是素数。
 
（2）将已知素数都进行倍数筛除，剩下最小的那个数就是素数。
 
看图理解吧：
 
 
 （想一下为什么？拿3，2和5举例自己想一下）
 
那么就用代码来求1到n之间的素数：
 
这里需要提前了解一下：（代码也标注的比较详细）
 
（1）我们要用一个bool数据类型的数组，数组的下标来表示1-n之间的数。
 
1）bool数据类型自己去查，只有c++有这个数据类型，如果非要用c也可以用char。
 
2）bool数据类型用来表示真假，在这里用真来标记bool数组的下标为素数，用假来表示下标不是素数。所以数组的要足够大。
 
（2）了解一下#include和它的memest函数，memset函数用于拷贝，再这里用它来给bool数组初始化为真。
 
ok，代码：
 
#include
#include//memest的头文件
const int N = 1e7+5;
//#define N 10000 //1e7+5用它不管
int cr[1000];//如果需要，用来存储素数
bool ch[N];//c++里面的一种数据类型，一个数据占一个字节，常用true表示真，false表示假
void as(int n)//埃氏晒法
{
    memset(ch,true,sizeof(ch));//c语言的库函数，将数据拷贝到另一个数据的字节里面
    int i,j;
    for(i=2; i<=n; i++)
    {
        if(ch[i])
        {
            for(j=2*i; j<=n; j+=i)//使筛除范围不大于n
            {
                ch[j]=false;
            }
        }
        
        //如果打印素数可以这样省了再循环
            if(ch[i])
                printf("%d ",i);
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    as(n);
    return 0;
}
 
埃氏筛优化： 
回到这张图
 
 
优化点1：
 
原理同最上面的优化1一样，在这里也就是如果要把1到n之间的素数筛选出来，只要把1到√n的素数进行倍数筛除就可以了。
 
优化点2：
 
每一次倍数筛除不再从二倍开始，而是从素数的平方开始，因为当一个的素数k（k够大），如果按照2*k，3*k，4*k（即2*2k）...这样从2倍开始一点点筛除的话，不难看出k*k之前的数一定是被k之前的素数筛除了一遍，这样就造成了重复就算浪费时间了。（聪明的人肯定也想出来了，k*k后面的还是会重复，所以埃氏筛的效率还不是最高对的）
 
ok，代码：
 
#include
#include//memest的头文件
const int N = 1e7+5;
//#define N 10000 //1e7+5用它不管
int cr[1000];//如果需要，用来存储素数
bool ch[N];//c++里面的一种数据类型，一个数据占一个字节，常用true表示真，false表示假
void ass(int n)
{
    memset(ch,true,sizeof(ch));
    int i,j,m=0;
    for(i=2;i*i<=n;i++)//(1)//根据根号的原理优化//缺点明显，不能存储素数到一个数组里，不能边筛边打印，因为i=根下n时结束循环
    //for(i=2;i<=n;i++)//(2)//放弃根号的原理方面存储数据和直接输出
    {
        if(ch[i])
        {
            //cr[m++]=i;如果按(2)存储数据
            for(j=i*i;j<=n;j+=i)//i*i也是小优化，可以避免i*i前面的合数再次被筛浪费时间
                ch[j]=false;
            //printf("%d ",i);//(2)的直接输出
        }
    }
    for(i=0;i<=n;i++)//如果按照（1）只能这样输出或存储素数
        if(ch[i]&&i!=1&&i!=0)
        printf("%d ",i);
}
int main()
{
    int n;
    scanf("%d",&n);
    ass(n);
    return 0;
}
 
欧拉筛 
核心思想：一个合数只会被筛选一次
 
主要依据：合数可以写成最小质因子（能被合数整除的最小素数）乘以最大公约数的形式。
 
方法：保证每一个合数只被最小质因子筛除
 
欧拉筛不像埃氏筛那么好理解，主要难理解的有这么两点：
 
（1）为什么就保证了每一个合数只被筛除一次。
 
（2）不会存在漏筛吗？
 
先看代码再谈：
 
#include
#include//memest的头文件
const int N = 1e7+5;
//#define N 10000 //1e7+5用它不管
int cr[1000];//如果需要，用来存储素数
bool ch[N];//c++里面的一种数据类型，一个数据占一个字节，常用true表示真，false表示假
void ol(int n)//欧拉筛
{
    memset(ch,true,sizeof(ch));//bool数组初始化
    int i,j,m=0;//m用于表示存储素数数组的下标
    for(i=2;i<=n;i++)//i控制的是最大公倍数
    {
        if(ch[i])//如果i为素数就把i存进已有素数
            cr[m++]=i;
        for(j=0;cr[j]*i<=n;j++)//cr[j]控制的是最小质因子//使cr[j]*i<=n
        {
           ch[cr[j]*i]=false;//筛去已有素数i倍的合数
           if(i%cr[j]==0)//保证每一个和数只被筛一次
            break;
        }
        if(ch[i])//可以在这里直接输出素数，也可以数出cr的素数数组
            printf("%d ",i);
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    ol(n);
    return 0;
}
 
在埃氏筛的基础上，看代码应该可以理解，那么就解决两个难理解的点就好了:
 
(1)我们是通过i%cr[j]如果等于0就结束对cr[j]后面素数的筛除，为什么那？根据依数zhi好好看公式，初中水平就可以看懂:
 
 
 
因为：i%cr[j]==0；
 
 
所以:i=k*cr[j]；
 
 
        cr[j+1]*i==k*cr[j]*[j+1];
 
 
设i2=k*cr[j+1]；
 
 
设合数 x=cr[j+1]*i==cr[j]*k*cr[j+1];
 
 
因为:x只能被最小质因子筛除，即只能被cr[j]的i2（i2=k*cr[j+1]）倍筛除筛除，所以如果在i时如果筛除了x，就会造成后面i2时重复筛选,同理可证也会造成cr[j+2]....也会重复。
 
 
所以在i%cr[j]==0时结束i倍的筛除。
 
 
 
 
（2）为什么不会漏筛？
 
为什么会思考这个问题那？不是每一个合数都保证了被最小质因子和最小约定数的筛除了吗？漏筛？确实会漏筛，因为漏筛的是素数。如果非要较劲可以去通过数学原理证明，也可以做个实验（在代码中加一个标记筛除一次标记一次，看看筛除了多少次，或者干脆直接把每次筛除的打印出来看看）。
 
 
 
最后思考一下，用筛法判断一个数是不是素数该怎么实现？
 
                                         for(talent=strive;stru>talent;strive++)
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5593139.html