算法-质数 约数

1.欧几里得算法（又称辗转相除法）用于计算两个数的最大公约数

//时间复杂度O(logn)
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

2.试除法判定质数

//时间复杂度O(sqrt(n))
bool is_prime(int x)
{
    if(x<2) return false;
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0) return false;
    }
    return true;
}

3.试除法分解质因数

//时间复杂度O(sqrt(n))
void divide(int x)
{
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)
        {
            int s=0;
            while(x%i==0) x/=i,s++;
            printf("%d %d\\n",i,s);
        }
    }
    if(x>1)
    {
        printf("%d 1\\n",x);
    }
}

4.朴素筛法(Eratosthenes)求素数

//时间复杂度O(nlogn)
//1-x的质数个数(x/lnx)
int primes[N],cnt;	// primes[]存储所有素数
int st[N];			// st[x]存储x是否被筛掉
void get_primes(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(st[i]) continue;
        primes[++len]=i;
        for(int j=i+i;j<=n;j+=i)
        {
            st[j]=true;
        }
    }
}