..质数..
先弄清楚我们在上小学时 学的概念。
1、什么是质因数？
-质因数是指能够整除给定正整数的质数。每个正整数都可以被表示为几个质数的乘积，这些质数就是该数的质因数。质因数分解是将一个正整数分解成若干个质数相乘的过程。例如，数字 12 的质因数分解是 2 × 2 × 3，因此 2 和 3 是 12 的质因数。
2、什么是质因数的底数与指数？
-底数（Base）：指的是质因数分解中的质数。这些质数是构成原数的不可再分的基本元素。例如，在质因数分解12的过程中，底数是2和3，因为12可以分解为2和3的乘积。
-指数（Exponent）：指的是在质因数分解中，每个质因数出现的次数。指数表示该质因数在原数中的“数量”。例如，数字12可以分解为 22×3122×31，这里2的指数是2，表示质因数2出现了两次；3的指数是1，表示质因数3出现了一次。
3、什么是合数？
-合数是一个大于1的自然数，它不是质数，也就是说，它除了1和它本身以外，至少还有一个正因数。换句话说，合数可以被分解为两个或更多较小的正整数的乘积。合数的判定方法通常是通过检查一个数是否有除了1和它本身以外的因数。如果一个数可以被除了1和它本身以外的任何数整除，那么这个数就是合数。
4、什么是因数？
-因数是指能够整除给定正整数的数。换句话说，如果一个数b能够被另一个数a整除，那么b就是a的因数。因数通常是指除了1和它本身以外的因数，因为1是所有正整数的因数。
质数
质数的判断
在判定一个数是否为质数时常用试除法
题目：866. 试除法判定质数 - AcWing题库
代码：
复杂度是严格的O(sqrt(n))
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=105;
int n,a[N];
bool check_prime(int x)
{
//1不是质数
if(x<2) return false;
//对于一个非质数的数而言，一定含有两个因数，所以只要枚举较小的那一个即可
for(int i=2;i<=x/i;i++)
{
if(x%i==0) return false;
}
return true;
}
int main()
{
cin >> n;
for(int i=0;i<n;i++)
{
cin >> a[i];
if(check_prime(a[i])) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}这里的 判定条件写为i <= x/i 而不写成i <= sqrt(x) 的原因是因为后者效率低，不写成i*i <= x 原因是因为防止i*i时溢出
分解质因数
分解质因数——试除法（O(sqrt(n))——>O(log2(n))~O(sqrt(n))）
从小到大枚举所有数
for(int i=2;i<=n;i++)
if(n%i==0)
{
int s=0;
while(n%i==0)
{
n/=i;
s++;
}
cout << i << s << endl;
}
在这里枚举的是所有因数，而不是枚举的所有质因数。
原因就是在枚举所有数的过程中，当枚举到i的时候，2~i-1之间的i的所有因数都被除干净了
所以这里所枚举的就是质因数。例如n=8的时，i=2就会把n置于0，枚举到i=4的时候已经n已经=1了。
由于n当中最多只包含一个大于sqrt(n)的质因子，即它本身
所以代码为：
for(int i=2 ;i <= n/i;i ++ )
if(n%i==0)
{
int s=0;
while(n%i==0)
{
n/=i;
s++;
}
cout << i << s << endl;
}
if(n>1) cout << n << 1 << endl;题目：867. 分解质因数 - AcWing题库
代码：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,a[105];
void print_prime(int x)
{
for(int i=2;i<=x/i;i++)
{
if(x%i==0)
{
int s=0;
//求底数的质数
while(x%i==0)
{
//这里如果质因数的质数不唯一，那么就逐个舍弃
x/=i;
s++;
}
cout << i << ' ' << s << endl;
}
}
//经过上述质因数的分解后，x>1的话，那么x就是一个质数。比如17、19...经过上述循环仍为它本身
if(x>1) cout << x << ' ' << 1 << endl;
//注意题目要求的格式
cout << endl;
return;
}
int main()
{
cin >> n;
for(int i=0;i<n;i++)
{
cin >> a[i];
print_prime(a[i]);
}
return 0;
}筛质数
两种算法，
1、朴素筛法：对2~n-1的数的倍数做标记，那么剩余没有被标记的即为质数。因为剩余的也就没有因子。
贴个图，一目了然
板子：
void get_prime(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i])
{
prime[res++]=n;
}
for(int j=i+i;j<=n;j+=i) st[j]=true;
}
}对朴素筛选的优化 ——埃氏筛
在筛选过程中只用质数去筛，因为一个数最小的因数就是质因数，证明：一个数的除了1之外最小的因数一定是质数吗？为什么？_百度知道 (baidu.com)
板子：
void get_prime(int n)
{
for(int i=2;i<=n;i++)
{
//如果被筛选后仍为false，则为质数
if(!st[i])
{
res++;
for(int j=2*i;j<=n;j+=i) st[j]=true;
}
}
}缺点：无论怎样优化都会有数被多次标记，进而增加复杂度
2、线性筛
用每个合数只会被最小的质因数筛掉。因为每个数的最小质因数只有一个，所以每一个数只会被筛一次，所以总体为线性。
板子：
void get_prime(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i]) a[res++]=i;
for(int j=0;a[j] <= n/i;j++)
{
st[a[j]*i]=true;
if(i%a[j]==0) break;
}
}
}题目：868. 筛质数 - AcWing题库
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,res,a[1000010];
//开个bool数组来记录当前数是否为质数
bool st[1000010];
void get_prime(int n)
{
for(int i=2;i<=n;i++)
{
//如果被筛选后仍为false,则为质数,我们就将其记录下来。
if(!st[i]) a[res++]=i;
//每一个数只会被它的最小质因子筛去
//枚举每一个质数
for(int j=0;a[j] <= n/i;j++)
/*
这里a[j]退出循环的条件我们展开来看：a[j]*i<=n如果a[j]再增加，那么a[j]*i的值
就会>n，筛n之外的非质数对于题干要求来说没什么意义
*/
{
/*
比如这里的i=27，那么在第一次会把st[2*27]筛出去，第二次把st[3*27]筛出去
第三次把st[5*27]但是第三次的筛选是没有任何意义的
因为5*27=45*3;所以5*27应该由它的最小质数3所筛去
*/
st[a[j]*i]=true;
//如果i%a[j]==0那么a[j]一定是i的最小质因子，如果不break掉，那么一定会造成后续的数重复被标记
if(i%a[j]==0) break;//a[j]一定是i的最小质因子，因为a[i]是从小到大进行枚举
}
}
}
int main()
{
cin >> n;
get_prime(n);
cout << res << endl;
return 0;
}
原文地址：https://blog.csdn.net/2301_80358171/article/details/140361143
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！