a^b%n 递归

int  quickpow(int a,int b,int n){
if(b==1){
return a;
}
else if(b%2==0){
int t = quickpow(a,b/2,n);
return t*t%n;
}
else {
int t = quickpow(a,b/2,n);
t = t*t%n;
t=t*a%n;
return t;
}
}

非递归

int quickpow(int a,int b,int n){
int res = 1;
while(b){
if(b%2==1){
res = res*a%n;
}
a=a*a%n;
b=b>>1;
}
return res;
}

线性筛

int v[MAXN],prime[MAXN];
void primes(int n){
 memset(v,0,sizeof(v));
//最小质因子
m=0;
//质数数量
for(int i = 2;i<=n;i++)
{
if(v[i]==0){
v[i]=i;
prime[++m]=i;
}
for(int j = 1;j<=m;j++){
//给i乘上一个质因子
if(prime[j]>v[i]||prime[j]>n/i){
break;
}
else{
v[i*prime[j]]=prime[j];
}
}
}
for(int i = 1;i<=m;i++){
cout<<prime[i]<<endl;
}
return ;
}