当前位置 博文首页 > KingKong.X ?的博客：素数筛选以及快速幂和慢速乘的实现
最大公约数
int gcd(int a,int b)//辗转相除法求最大公约数
{
while(b)
{
int c=a%b;
a=b;
b=c;
}
return a;
}
最小公倍数
由于a*b有可能会溢出，因此可以先除再乘，因为GCD是它们的最大公约数，因此a/GCD一定是个整数
int lcm(int a,int b,int GCD)//最小公倍数=两个数的乘积/最大公约数
{
return a/GCD*b;
}
快速幂和慢速乘
long long int fastPow(long long int a,long long int b,long long int p)//求(a^b)%p
{
long long int ans=1;
while(b)
{
if(b&1) ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
long long int slowMul(long long int a,long long int b,long long int p) //a*b%p
{
long long int ans=0;
while(b)
{
if (b & 1) ans = (ans + a) % p;
a = (a + a) % p;
b >>= 1;
}
return ans;
}
素数的判定，时间复杂度是O(sqrt(n))
bool isPrime(int n)//判断是否是素数
{
if(n<=1) return false;
for(int i=2;i<=sqrt(n);i++)
{
if(n%i==0) return false;
}
return true;
}
埃氏筛选找素数 时间复杂度O(nloglogn)
const int maxn=1001;
bool p[maxn]{0};//如果i为素数，那么p[i]为false,否则为true
int prime[maxn];//存放素数
int pnum=0;//素数的个数
void findPrime()//获取2-1000的素数表
{
for(int i=2;i<maxn;i++)
{
if(!p[i])//如果p[i]是素数，那么它的倍数都不是素数
{
prime[pnum++]=i;
for(int j=i*i;j<maxn;j=j+i)
{
p[j]=true;
}
}
}
}
欧拉筛法找素数 时间复杂度O(n)
const int maxn=1001;
bool p[maxn]{0};//如果i为素数，那么p[i]为false,否则为true
int prime[maxn];//存放素数
int pnum=0;//素数的个数
void findPrime()
{
for(int i=2;i<maxn;i++)
{
if(!p[i]) prime[pnum++]=i;
for(int j=0;j<pnum;j++)
{
if(i*prime[j]>maxn) break;
p[i*prime[j]]=true;
if(i%prime[j]==0) break;
}
}
}
