质数的判定——试除法——O(sqrt(n))

//本质上是找x在2～x-1有没有因数
for (int i = 2; i <= x / i; i ++ )
{
    if (x % i == 0) return false;
}

不推荐的写法

for (int i = 2; i <= sqrt(x); i ++ ) //每次一个sqrt太慢
for (int i = 2; i * i <= x; i ++ )   //i*i爆int

分解质因数——试除法——O(sqrt(n))

//O(n)
for(int i = 2; i <= n; i++)
{
    if(n % i == 0)
    {
        int s = 0;
        while(n % i == 0) { n /= i; s++; }
        cout<<i<<' '<<s;             //质因数本身以及出现几次
    }
}

又因为，n中最多只包含一个大于sqrt(n)的质因子

//O(sqrt(n))
for(int i = 2; i <= n / i; i++)
{
    if(n % i == 0)
    {
        int s = 0;
        while(n % i == 0) { n /= i; s++; }
        cout<<i<<' '<<s;             //质因数本身以及出现几次
    }
}
if(n > 1) cout<<n<<' '<<1;

筛选素数————O(n)

朴素方法：如果一路从2筛到i，i还没被筛出去，那么2～i-1中间不存在i的因数，所以i是质数

//O(nlogn)
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;
}

一个小优化：每次只需要拿掉质数的倍数即可，因为和数及其倍数都可以归于质数的倍数，于是埃筛就来了

//O(nlonglongn)
//约为O(n)
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;
    }
}

再进一步：使n内的合数只会被它的最小质因子筛掉，优化了了一个数筛多次的情况，于是欧拉筛就来了

//严格O(n)
//穷举n内的所有素数，再枚举n内所有素数的倍数（每个只出现一次），从而覆盖n内所有的数
//比如进行到i == 5时primes数组喜提新成员5
//此时5*1是5 5*2 5*3分别被2和3筛掉 5*4归2管 5*5由5自己筛 5*6等primes5下一次循环
//所以每个质数归primes，每个合数只会被它的最小质因子筛掉，达到O(n)效果
for(int i = 2; i <= n; i++)
{
    if(!st[i]) primes[cnt ++] = i;
    for(int j = 0; primes[j] <= n / i; j++) //为了避免爆int的primes[j] * i <= n
    {
        st[primes[j] * i] = 1;
        if(i % primes[j] == 0) break;       //这个break可以保证primes[j]绝对小于等于i的最小质因子
        //当i能整除primes[j]时，i*primes[j+1]肯定是prime[j]的倍数，会被primes[j]筛一遍
        //那等会i*primes[j + 1]又被primes[j + 1]筛一次，导致重复
    }
}