质数的判定——试除法

int is_prime(int x)
{
    if(x<2)
        return 0;
    for(int i=2;i<=x/i/*关键是到x/i,而不是x-1*/;i++)
    {
        if(x%i==0)
            return 0;
    }
    return 1;
}

分解质因数——试除法

void divide(int x)
{
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)//i一定是质数
        {
            int s=0;
            while(x%i==0)
            {
                x/=i;
                s++;
            }
            printf("%d %d\n",i,s);
        }
    }
    if(x>1)
        printf("%d %d\n",x,1);
}

筛质数

void get_primes(int n)//埃氏筛法(O(nloglogn))
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            primes[cnt++]=i;
            for(int j=i+i;j<=n;j+=i)
                st[j]=1;
        }

    }
}

void get_primes(int n)//埃氏筛法优化(O(nlogn))
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            primes[cnt++]=i;//存储质数
            for(int j=i;j<=n/i;j++)
            st[i*j]=1;//从i*i开始
        }
    }
}

//n只会被最小质因子分解掉
/*
i%primes[j]==0
    primes[j]一定是i的最小质因子,primes[j]一定是primes[j]*i的最小质因子
i%primes[j]!=0
    primes[j]一定小于i的所有质因子,primes[j]一定是primes[j]*i的最小质因子

对于一个合数x,假设primes[j]是x的最小质因子，当i枚举到x/primes[j]
*/

void get_primes(int n)//线性筛法(O(n))
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
            primes[cnt++]=i;
        for(int j=0;primes[j]*i<=n;j++)
        {
            st[primes[j]*i]=1;
            if(i%primes[j]==0)//primes[j]一定是i的最小质因子
                break;
        }
    }
}