质数(866,867,868)
前导知识
1:算术基本定理:任何一个大于1的自然数可以分解成一些质数的乘积。且表示方式唯一。
2:由于n只有一个的质因数大于√n。反证,如果有两个,那么相乘必然大于n。
试除法判定质数(866)
解题思路
我们先看看质数的定义:质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。
由这个定义我们可以由这个定义想出一个朴素的判断方法——看看这个数能不能被在比1大比自身小的数整除
代码如下:
bool func(int a)
{
if(a == 1 || a == 0)return false;//0和1既不是质数也不是和数
for(int i = 2;i < a;i ++)
{
if(a % i == 0)//判断整除
{
return false;
}
}
return true;
}
但是这样时间还是太长了,有很多数其实可以不用判断整除的。
我们可以利用质数的特性——前导知识中提到的:由于n只有一个的质因数大于√n。反证,如果有两个,那么相乘必然大于n。
一个数可以表示为一个大数和一个小数所以大于且不等于n的sqrt(n)的质因数肯定会与其他较小的数整除,最大要判断的是两个一样的数相乘就是sqrt(n)*sqrt(n),所以i只需要判断2 ~ sqrt(n)的数。
源代码
#include <iostream>
#include <cstdio>
using namespace std;
bool func(int a)
{
if(a == 1 || a == 0)return false;//0和1既不是质数也不是和数
for(int i = 2;i <= a / i;i ++)
{
if(a % i == 0)
{
return false;
}
}
return true;
}
int main()
{
int n;
cin >> n;
for(int x = 0;x < n;x ++)
{
int a;
scanf("%d",&a);
bool re = func(a);
if(re)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
return 0;
}
分解质因数(867)
解题思路
我们可以一个一个数从小到大试除。这里从小到大非常重要,因为这样会先试除小的数,然后在原本的数里把这个质因数除掉,就会把这个质数的倍数即和数自动过滤掉了。
最后有一点比较重要,因为这次不是判断质数,除了从2~sqrt(n)要试除还需要考虑可能有一个个大于sqrt(n)的质数,我们又可以利用前导知识中的算术基本定理:任何一个大于1的自然数可以分解成一些质数的乘积。且表示方式唯一。所以试除剩下来的数如果不是1的话这个数就是最后的质因数。
源代码
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int n;
cin >> n;
for(int x = 0;x < n;x ++)
{
int a;
scanf("%d",&a);
int b = a;
for(int i = 2;i <= a / i;i ++)//i是质因数本身(底数)
{
if(b % i == 0)
{
int s = 0;//该质因数数量(指数)
while(b % i == 0)//统计数量
{
s ++;
b /= i;
}
printf("%d %d\n",i,s);
}
}
if(b > 1)
{
printf("%d 1\n",b);
}
printf("\n");
}
return 0;
}
质数筛(868)
原题链接:868. 筛质数 - AcWing题库
解题思路
面对这个问题我们第一个想到的肯定是一个非常朴素的想法——每个数都判断是不是质数。但是想想就知道这样肯定会很费时间。
我们可以利用埃氏筛法:要得到自然数n以内的全部素数,必须把不大于sqrt(n)的所有素数的倍数剔除,剩下的就是素数。
我们可以创建一个数组记录哪些是质数哪些是和数。我们从1~n从小到大遍历,遍历到i时i前的所以素数的倍数已经被剔除了,我们就可以通过那个数组判断i是不是质数,如果i是质数就把i的倍数都剔除。
源代码
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1000010;
int n;
bool st[N];//是不是质数
int re;
int main()
{
cin >> n;
re = 0;
for(int i = 0;i <= n;i ++)st[i] = true;//刚开始默认是质数
for(int i = 2;i <= n;i ++)
{
if(st[i])
{
re ++;//质数数量+1
for(int j = i;j <= n;j += i)//质数的倍数都是和数
{
st[j] = false;
}
}
}
cout << re;
return 0;
}