1.质数——筛质数
题目:给定一个正整数n,请你求出1~n中质数的个数。
(1)朴素筛法O(nlogn)
算法核心:把每个数的所有倍数筛掉
调和级数:1 + 1/2 + 1/3 +…+ 1/n = lnn + c(c欧拉常数=0.577)
算法时间复杂度:最外层遍历整个数组是n(其实不用管,只用看内部总次数即可),内部循环总次数是n/2,n/3,n/4…1,累加得n(1/2 + 1/3 + 1/4 +…+1/n)=nlnn=nlogn
void get_prime(int x)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++] = i;
for(int j = i + i ; j <= n ; j += i) st[j] = true;
}
}
(2)埃式筛法O(nloglogn)
算法核心:把每个质数的所有倍数筛掉
质数定理:1~n中由n/logn个质数
算法时间复杂度:由(1)可得:O(nlonglongn)当数据不是足够大时与O(n)接近
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (st[i]) continue; //st如果是true 说明被筛过,那么它的倍数肯定被筛过,所以直接跳过
//接下来对该质数的所有倍数进行筛选
primes[cnt ++ ] = i;
for (int j = i + i; j <= n; j += i)
st[j] = true;
}
}
(3)线性筛法O(n)
算法核心:x只会被它的最小质因数筛去,即每个数字只被筛选一次,因此是线性的n。
证明每个x都能被筛掉:
对于一个合数x,x一定存在一个最小质因子,假设pj是x 的最小质因子,当i枚举到x/pj时,x就被筛了,因为x只有一个最小质因数,因此每个数字只被筛选一次。
算法时间复杂杂度:因为每个数只被筛过一次,因此为O(n)
void get_prime(int x)
{
for(int i = 2 ; i <= x ; i++)
{
if(!st[i]) primes[cnt ++] = i;
/**
for循环判断语句中不需要j<cnt。分两种情况。
1.i为合数,当primes[j]取到i的最小质因子时就break 此时 j<cnt
2.i为质数,当primes[j]的值和i想当时就break 此时j == cnt-1
**/
for(int j = 0 ; primes[j] <= x / i ; j++)
{
st[primes[j] * i] = true; //筛去primes[j]的倍数
/*
针对st[primes[j] * i] = true;本质上分两种情况
1.i%pj == 0, 因为primes[j]是顺序遍历,因此当当一次模为零时,primes[j]一定为i的最小质因
子,primes[j]也一定为primes[j]*i的最小质因子
2.i%pj != 0, 同样因为primes[j]是顺序遍历,primes[j]一定小于i的所有质因子
所以primes[j]也一定为primes[j]*i最小质因子
*/
if(i % primes[j] == 0) break;//当primes[j]是i的最小质因数时break(为了
//遵守算法的核心,避免重复的筛选)。如果继续用primes[j+1]去筛选,此时,
//primes[j+1]大于i的最小质因子,那么也同样不是primes[j+1]*i的最小质因子
}
}
}