素数

素数打表
 

const int maxn=1000005;
const int _maxn=78499+5; //1000000内拥有的素数
 
int prime[_maxn];
bool vis[maxn];//待打表完成后，vis数组中将保存素数的直接判断
 
int sum[maxn];
 
int get_prime() { //高效素数打表
    me(vis,true);
    vis[0]=vis[1]=false;
    int cnt=0;
    for(int i=2;i<maxn;i++) {
        if(vis[i]) prime[cnt++]=i;
 
        for(int j=0;(j<cnt)&&(i*prime[j]<maxn);j++) {
            vis[i*prime[j]]=false;
            if(i%prime[j]==0)break;
        }
    }
    return cnt;
}

GCD

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