质数筛
暴力版:
- bool prime(int n)
- {
- for(int i=2;i<=sqrt(n);i++)
- if(n%i==0) return false;
- return true;
- }
如果给定区间 1 到 n, 判断每一个数是不是质数, 每个数都要从 2 开始暴搜, 就某得灵魂.
普通筛:
- bool isprime[maxn];//1 代表是质数, 0 代表不是
- void judge()
- {
- memset(isprime,true,sizeof(isprime))// 默认全都是质数
- for(int i=2;i<=maxn;i++)
- {
- if(isprime(i)){//i 是质数
- for(int j=2;j*i<=maxn;j++)// 那么 i 乘一个数就不是质数了
- isprime[j]=0;
- }
- }
- }
这样就是一个线性的过程, 从 2 开始到 n 筛, 灵魂注入了一点, 但弊端还是有, 很多数被重复判断了.
真 • 线性筛 (欧拉筛):
- bool isprime[n];//1 代表是质数, 0 代表不是
- int prime[n];// 素数数组, 从小到大装着 1 到 n 的素数
- void judge()
- {
- memset(isprime,true,sizeof(isprime))// 默认全都是质数
- int tot=0
- for(int i=2;i<=n;i++)
- {
- if(isprime(i))// 是质数
- prime[tot++]=i;// 存到素数数组里
- for(int j=0;j<tot&&prime[j]*i<n;j++)
- {
- isprime[ i * prime[j] ]=false;
- if(i%prime[j]==0)// 保证每个合数都被它的最小素数筛掉
- break;
- }
- }
- }
这个的思想和普通筛一样, 但却避免了一个合数被多次判断.
慢慢来, 首先 i 无论是不是素数, i 乘一个 prime[j] 肯定就不是素数, 如何避免重复筛呢, 首先合数是一定有质因子的 (合数能分解质因数), 所以要找到 j 的界限, 保证一个合数只被判断一次, 线性筛是从小到大的, 自然是找每个合数的最小质因子了.
结论: 如果 i 能整除 prime[j] , 此时 j 就不能 ++ 了, i *prime[j+1] 肯定会被 prime[ j] 乘某个数筛掉;
证明: i 若能整除 prime[ j]
则 i=k * prime[j]
则 i *prime[ j+1]=k*prime[ j ] *prime[j+1]
则 i * prime[ j + 1] = k' *prime[ j ]
所以每个合数都只会被它的最小质因数筛掉.
莫比乌斯筛
来源: http://www.bubuko.com/infodetail-3049002.html