一.质数的判定：
bool isprime(int x)
{
if(x<=1)
return false;
for(int i=2;i<=x/i;i++)
{
if(x%i==0)
return false;
}
return true;
}
2.质因数的分解：
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--)
{
int x;
cin>>x;
for(int i=2;i<=x/i;i++)
{
int p=0;
while(x%i==0)
{
x/=i;p++;
}
if(p)
cout<<i<<' '<<p<<endl;
}
if(x>1)
cout<<x<<" "<<1<<endl;
cout<<endl;
}
return 0;
}
?
基本原理：从小到大将每个质数的倍数筛去
若某个数没有被它前面的数筛掉，那么它一定是质数。
原因：它不是前面的2~p-1中任何一个数的倍数，那么它是质数
时间复杂度：n*log(log(n))，接近线性
const int N = 1e6+5;
bool isprime[N];
int prime[N];
int cnt;
void init(int n)
{
isprime[1]=true;
for(int i=2;i<=n;i++)
{
if(!isprime[i])
{
prime[++cnt]=i;
for(int j=i+i;j<=n;j+=i)
isprime[j]=true;
}
}
}
基本原理：每个数只会被它最小的质因数筛掉，那么每个数只会被筛一次，所以时间复杂度为o(n)
const int N = 1e6+5;
bool isprime[N];
int prime[N];
int cnt;
void init(int n)
{
isprime[1]=true;
for(int i=2;i<=n;i++)
{
if(!isprime[i])
prime[cnt++]=i;
for(int j=0;prime[j]<=n/i;j++)
{
isprime[prime[j]*i]=true;
if(i%prime[j]==0)
break;
}
}
}
4. 米勒罗宾素数检测法（快速判断大质数）
适用范围：较大数的较快素性判断
原理是费马小定理：如果p是素数，则a ^ (p-1)%p == 1，加上二次探测定理：如果p是一个素数，则x^2%p==1的解为，则x=1或者x=n-1。
一次检测中：
主要是把一个数n的n-1分解成d*2^ r的形式，其中d为奇数，正向过程是a^ n%p如果是1，就继续分解
a^ (n/2)%p，（a为一个与n互素的数）看是否为1,；如果是n-1就停止分解，说明至此无法判断是否为素数；如果不等于这两个值，则一定为合数。而在写代码过程是这个过程的逆向过程，先分解到底，看最后这个a^d%p是否为1或n-1，如果是说明已经分解到底了，也就是通过了此次素性测试。如果不是，说明在正向过程中出现了要么a的某次方为n-1，根据算法停止了检测过程；要么就是中间的某一个结果不等于这两个数，那么就是合数。就从最后往前面推，每一步看满不满足上述条件。直到判断为合数或者终止检测的那一步。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll q_mul(ll a,ll b,ll p)
{
ll ans=0;
while(b)
{
if(b&1)
ans=(ans+a)%p;
a=(a<<1)%p;
b>>=1;
}
return ans;
}
ll q_pow(ll a,ll b,ll p)
{
ll ans=1;
while(b)
{
if(b&1)
ans=q_mul(ans,a,p);
a=q_mul(a,a,p);
b>>=1;
}
return ans;
}
bool Miller_Rabin(ll n){
if(n==2)return true;
if(n<2||!(n&1))return false;
int t=2,r=0;
ll m=n-1;
while(m%2==0){
r++;
m>>=1;
}
srand(100);
while(t--)
{
ll a=rand()%(n-1)+1;
ll x=q_pow(a,m,n),tmp=0;
for(int i=0;i<r;i++){
tmp=q_mul(x,x,n);
if(tmp==1&&x!=1&&x!=n-1)return false;
x=tmp;
}
if(tmp!=1)return false;
}
return true;
}
void get_ans(int n)
{
vector<int> ans;
for(int i=1;i<=n/i;i++)
{
if(n%i==0)
{
ans.push_back(i);
if(i!=n/i)
ans.push_back(n/i);
}
}
sort(ans.begin(),ans.end());
for(auto x:ans) cout<<x<<" ";
cout<<endl;
}
2. 求约数个数或约数之和
原理：唯一分解定理
任意正整数 n = (a1 ^ p1) * (a2 ^ p2) * (a3 ^ p3) … * (ak ^ pk)
其中a1…ak均为质数
那么约数之和 sum=(p1+1) * (p2+1) * (p3+1) … (pk+1)
即对第一个质因子可以有p1+1种选法，一直到对第k个质因子，有pk+1种选法，把选中的数乘起来就是总约数个数
?
#include<iostream>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int mod =1e9+7;
int main()
{
int n;
cin>>n;
unordered_map<int,int> mp;
while(n--)
{
int x;
cin>>x;
for(int i=2;i<=x/i;i++)
while(x%i==0)
{
x/=i;
mp[i]++;
}
if(x>1)
mp[x]++;
}
ll ans=1,ans2=1; //分别为约数个数，约数之和
for(auto x: mp)
{
int t=x.first,tt=x.second;
ll res=1;
while(tt--) res=(res*t+1)%mod;
ans=ans*res%mod;
ans2=ans2*(x.second+1)%mod;
}
cout<<ans<<" "<<ans2<<endl;
return 0;
}
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int lcm(int a,int b)
{
return a/gcd(a,b)*b;
}
三、欧几里得算法
1. 扩展欧几里得算法
（1）求ax+by=gcd(a,b)的任意一组解：
因为gcd(a,b)=gcd(b,a%b)
为计算方便 , 递归的时候交换x,y位置，那么原式就变为
by+(a%b)x=gcd(a,b)
=>by + ( a - a / b (下取整) * b) * x = gcd(a,b)
=>ax + b(y - a / b * x) = gcd(a,b)
?
#include<iostream>
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x=1;y=0;
return a;
}
int r=exgcd(b,a%b,y,x);
y-=a/b*x;
}
int main()
{
int n;
cin>>n;
while(n--)
{
int x,y,a,b;
scanf("%d%d",&a,&b);
int r=exgcd(a,b,x,y);
printf("%d %d\n",x,y);
}
return 0;
}
（2）求ax+by=c的解
若c%gcd(a,b)！=0那么无解
根据上面求出一组x0, y0满足a * x0 + b * y0 = gcd(a,b)
令d=c/gcd(a,b), t=c/d
ax0+by0=d
ab/d+ax0-ab/d+by0=d
a(x0+b/d)-b(y0-a/d)=d
两边同时乘以t， 即解得 x=(x0+b/d)*t, y=(y0-a/d)*t
#include<iostream>
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x=1;y=0;
return a;
}
int r=exgcd(b,a%b,y,x);
y-=a/b*x;
}
int main()
{
int a,b,c,x0,y0,x,y;
scanf("%d%d%d",&a,&b,&c);
int d=exgcd(a,b,x0,y0);
if(c%d!=0)
printf("no solution\n");
else
{
int t=c/d;
x=(x0+b/d)*t;
y=(y0-a/d)*t;
printf("x=%d y=%d\n",x,y);
}
return 0;
}
目前学的不多，后续会根据自己的学习进度慢慢让这一片博客更加的完善。