素数(质数)
定义:1不是素数,素数是指大于1的自然数,除了1和该数自身外,无法被其他自然数整除的数。
(1)判断一个数是否为素数
方法一:枚举取余法(最简单最好理解)
顾名思义就是把n的所有因素组合按照素数的要求全部枚举一遍,
也就是范围2~n-1之间的所有数,不包括本身,
举个例子:
4可以由2 * 2 = 4和1 * 4 = 4得到因数2,2或1,4;
我们就是除了含有4本身的组合以外其他所有两个数相乘等于4的因数组合全部枚举出来
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
//判断一个数,是否为素数,就找从2~n-1的所有数看是否能跟n整除
int n;
scanf("%d",&n);
//如果输入的数不在自然数范围或者等于1,都不是质数,直接结束循环
if(n <= 1)
{
printf("No");
return 0;
}
//特判完以后,我们开始判是否为素数
int flag = 1; //flag作为素数筛选过程中的标记,初始为1先默认为素数
for(int i = 2;i < n;i ++) //这里是2~n-1的遍历
if(n % i == 0) flag = 0; //不是素数就标记为0
if(flag) printf("Yes"); //素数标记为1(或标记为非0)说明是素数
else printf("No"); //标记为0说明不是
return 0;
}
方法二:
我们对方法一进行优化:
举个例子:
4可以由2 * 2 = 4和1 * 4 = 4得到因数2,2或1,4;
我们会发现我们的目的是找出一组不含1和4本身的因数组合,
但是方法一是把不含1和4的每一个因数组合的每一个数都枚举一遍,
所以运行效率就显得不高效,我们仔细观察其实只需要把每一组
符合素数要求的因数组合找出其中一个因数即可,不需要两个都找出来,
最后,我们会发现每组只找到一个因数的话,存在一个规律就是
每组都会含有一个不大于4自身的1/2的这么一个因数,
所以只需要把枚举区间缩小到原来的1/2,就可以达到同样的效果!
所以我们可以利用这个思想来对方法一代码进行优化.(如下)
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
//判断一个数,是否为素数,就找从2~n-1的所有数看是否能跟n整除
int n;
scanf("%d",&n);
//如果输入的数不在自然数范围或者等于1,都不是质数,直接结束循环
if(n <= 1)
{
printf("No");
return 0;
}
//特判完以后,我们开始判是否为素数
int flag = 1; //flag作为素数筛选过程中的标记,初始为1先默认为素数
for(int i = 2;i <= n/2;i ++) //这里是2~n/2的遍历
if(n % i == 0) flag = 0; //不是素数就标记为0
if(flag) printf("Yes"); //素数标记为1(或标记为非0)说明是素数
else printf("No"); //标记为0说明不是
return 0;
}
方法三:
我们对第二种方法进行优化:
举个例子:
16可以由1*16,2*8和4*4得到因数1,16和2,8和4,4;
看懂方法二的思想以后,我们再来找规律,
发现每组因数组合其中都会包含一个因数不大于16本身的开方4的这么一个因数,
那么,我们只需要再一次把枚举区间缩小到方法一区间的开平方根,就再一次缩小区间完成优化
所以我们可以利用这个思想来对方法二代码进行优化.(如下)
#include <iostream>
#include <stdio.h>
#include<math.h> //这次优化需要用到数学函数
using namespace std;
int main()
{
int n;
scanf("%d",&n);
//如果输入的数不在自然数范围或者等于1,都不是质数,直接结束循环
if(n <= 1)
{
printf("No");
return 0;
}
//特判完以后,我们开始判是否为素数:
/*注意这里有个小细节,我把开根号放在循环外面,
是因为如果直接放在循环上会导致每一次循环判断条件的时候,
都会执行一遍sqrt(n),毕竟这是一个调用函数,调用次数过多就影响时间效率,记住就好*/
int flag = 1,tmp = sqrt(n);
for(int i = 2;i <= tmp;i ++) //注意:这里是最最容易出错的,很多人忘记带上tmp本身,写成了i<tmp犯了最严重的错误,一定要留心!!
if(n % i == 0) flag = 0;
if(flag) printf("Yes");
else printf("No");
return 0;
}
方法四:
把上面的写法写成一个通用函数模板:
#include <iostream>
#include <stdio.h>
#include<math.h> //这次优化需要用到数学函数
using namespace std;
int judge(int n) //返回0即为非素数,1即为是素数
{
if(n <= 1) return 0;
int flag = 1;
for(int i = 2;i <= sqrt(n);i ++) //这里可以写优化,也可以不优化,看题目要不要求时间复杂度
if(n % i == 0) flag = 0;
return flag;
}
int main()
{
int n;
scanf("%d",&n);
if(judge(n)) //函数返回值是1就是素数
printf("Yes");
else //函数返回值是0就不是素数
printf("No");
return 0;
}
OK,到这,你已经入门了,我开始正式的筛素数了!!
(2)求给定区间以内的所有素数
最基础的就是输入一个n求1~n以内的所有素数(把这种类型学会,给你一个[m,n]区间你也会写)
方法一:试除法(最慢的算法也就是基于最上面的方法一改写的)
这里不展开细讲了,因为最上面方法一讲的很清楚,这里只是套了一个外层循环,特判了一下而已
#include <iostream>
#include <stdio.h>
#include<math.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
for(int i = 2; i <= n; i ++ ) //1又不是素数直接从2开始跑,如果n<=1那循环更进不去所以不用担心
{
int flag = 1;
for(int j = 2;j < i;j ++)
if(i % j == 0)
flag = 0;
if(flag)
printf("%d ",i);
}
return 0;
}
方法二:减半法(基于最上面的方法二改写的)
参考最上面的方法二
#include <iostream>
#include <stdio.h>
#include<math.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
for(int i = 2; i <= n; i ++ ) //1又不是素数直接从2开始跑,如果n<=1那循环更进不去所以不用担心
{
int flag = 1;
for(int j = 2;j < i;j ++) //注意这里!减半了试除范围
if(i % j == 0)
flag = 0;
if(flag)
printf("%d ",i);
}
return 0;
}
方法三:开根号法(基于最上面的方法三改写的)
代码中需要把开根号放在外层循环里面这个小细节跟最上面方法三的代码里面写的有
#include <iostream>
#include <stdio.h>
#include<math.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
for(int i = 2; i <= n; i ++ ) //1又不是素数直接从2开始跑,如果n<=1那循环更进不去所以不用担心
{
int flag = 1;
int tmp = sqrt(i); //把开根号单一放入一个临时变量tmp,节省调用函数的时间开销
for(int j = 2;j <= tmp;j ++)
if(i % j == 0)
flag = 0;
if(flag)
printf("%d ",i);
}
return 0;
}
方法四:去偶开根号法(对开根号法进一步优化)
想不到吧,我还能优化hh,原理很简单因为所有素数当中只有2是唯一的偶数,那就好办了,因为我们要在一个区间里面筛出所有素数,所以直接除了2以外跳过区间里面所有偶数就再一次达到优化效果!
#include <iostream>
#include <stdio.h>
#include<math.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
if(n >= 2) //把2单一拿出来特判一下就行,只要区间包含2就先输出
printf("2 ");
for(int i = 3; i <= n; i += 2) //没有了2,就可以放心跳着循环
{
int flag = 1;
int tmp = sqrt(i); //把开根号单一放入一个临时变量tmp,整体来看更节省时间
for(int j = 2;j <= tmp;j ++)//这里最容易出错,一定要注意小于号还是小于等于号!!!
if(i % j == 0)
flag = 0;
if(flag)
printf("%d ",i);
}
return 0;
}