数学小总结

数论

感觉数论的核心就是任意的非素数都可分解为某个素数的乘机

筛法

埃氏筛法

for(int i=2;i<=n;i++)//枚举2~n所有数并找出素数
{
    if(!st[i])primes[cnt++]=i;//如果当前枚举到的数没有被之前筛掉，那么它就是素数
    else break;//这是个优化，没有这个优化为nlogn，加上之后就是nloglogn
    for(int j=2;j<=n;j+=i)//枚举当前数的所有倍数，所以枚举出来的都是和数
        st[j]=true;
}

线性筛法

for(int i=2;i<=n;i++)//筛选2~n的所有素数
{
    if(!st[i])primes[cnt++]=i;//如果当前数未被前面的筛掉，那么就是素数
    for(int j=0;primes[j]*i<=n;j++)//枚举小于n的所有已选出素数
    {
        st[primes[j]*i]=true;当前数可被分解为i*primes[j]，所以不是素数
        if(i%primes[j])break;到此如果i可以被已选出的素数分解，则进行下一轮
    }
}