质数、约数详解

质数

含义：除了1和他本身外，不能被其他自然数整数的数叫做质数，否则为合数

注：1既不是质数也不是合数

试除法判断素数

思想：对于一个数n，由于只有1和他本身能被整除，那么我们只用枚举2~n-1看是否出现被整除的情况，如果没有说明是素数

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){int x;cin>>x;//特判1if(x==1){cout<<"No"<<endl;continue;}bool f=true;//暴力从2~x-1for(int i=2;i<=x-1;i++){if(x%i==0){f=false;break;}}if(f)cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;
}

如果对于一个数x，可以被n整除，商为y，那么n=x*y，设x<=y，那么我们只用枚举x，如果n可以被x整除，那么也可以被y整除。所以对于上面判断方法可以优化：只用看在前半部分的数能否被n整除即可

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){int x;cin>>x;if(x==1){cout<<"No"<<endl;continue;}bool f=true;for(int i=2;i*i<=x;i++){if(x%i==0){f=false;break;}}if(f)cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;
}

那么上面的方法也有问题，如果i为1e9，那么ii就会发生溢出，不能和x比了。所以我们把ii<=x换为i<=x/i，这样就不会发生溢出了

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){int x;cin>>x;if(x==1){cout<<"No"<<endl;continue;}bool f=true;for(int i=2;i<=x/i;i++){if(x%i==0){f=false;break;}}if(f)cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;
}

分解质因数

根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。

$n=p_1^{x_1}\times p_2^{x_2}\times p_3^{x_3}...\times p_n^{x_n}$

pi代表质因数，xi代表指数

那么我们将他的因数i从小到大枚举，如果可以整除i，那么我们就将x一直除以i到不能除为止，然后输出i和指数（除以i的次数），然后再继续枚举。由于在前面将所有的整除的因数都除了，可以保证后来所能整除的因数都为质因数。

进一步优化：枚举可以不用枚举到x-1，可以枚举到$\sqrt{x}$,相当于枚举了n=x*y，x<=y中的x。

并且可以证明对于x，只能有一因数大于 $\sqrt{x}$：运用反证法，如果有两个因数大于$\sqrt{x}$，那么相乘就大于x，不等于x。

到最后如果剩下的数>1，说明剩下的数是唯一一个大于$\sqrt{x}$的因数。

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){int x;cin>>x;for(int i=2;i<=sqrt(x);i++){if(x%i==0){int ans=0;while(x%i==0){x/=i;ans++;}cout<<i<<" "<<ans<<endl;}}if(x>1)cout<<x<<" "<<1<<endl;cout<<endl;return 0;
}

埃式筛法筛质数

求出1~n中的所有质数的个数

时间复杂度O（nlog（logn））

思想：从2~n开始枚举，每次碰到素数记录一下，并且将他的倍数（合数）给筛掉，那么可以保证后面没有被筛掉的都是素数

	cin>>n;int con=0;for(int i=2;i<=n;i++){if(!st[i]){st[i]=true;prim[++con]=i;for(int j=i;j<=n;j+=i)st[j]=true;}}cout<<con;

约数

约数也叫因数，如果n能被m整除，那么m就叫做n的约数

试除法求约数

给定n个数ai，求每个数的约数，并从小到大排序输出

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=1e6+10;
int prim[N];
bool st[N];
int main(){cin>>n;vector<int> v;while(n--){v.clear();int x;cin>>x;for(int i=1;i<=x/i;i++){if(x%i==0){v.push_back(i);if(x/i!=i)v.push_back(x/i);}}sort(v.begin(),v.end());for(int i=0;i<v.size();i++){cout<<v[i]<<" ";}cout<<endl;}return 0;
}

最大公约数

最大公约数：两个或多个整数共有约数中最大的一个数，也称最大公因数，最大公因子

用(a，b)表示a和b的最大公因数：有结论(a，b)=(a，ka+b)，其中a、b、k都为自然数。

也就是说，两个数的最大公约数，将其中一个数加到另一个数上，得到的新数，其公约数不变.

那么我们就可以将(a，ka+b)，通过（ka+b）%a的方式，变为b，那么就变为（a，b）了

基本思路就是取余，一直取到其中一个结果为0的时候就可以结束，剩下的一个数就是最大公约数

int gcd(int a,int b){return b?gcd(b,a%b):a;
}