网站开发的解决方案,一个网站源代码概多大,网络科技公司网站建设策划,python做网站步骤题目
AcWing 868. 筛质数 题解
方法一#xff1a;朴素筛法 及其优化#xff1a;埃氏筛 从2~n枚举 i,再从小到大枚举所有已知的质数 primes[j],筛掉合数 i*primes[j],遇到新的质数就入队 枚举所有小于n的数i,将i的所有倍数筛掉。 筛完后剩下的数就是质数。 朴素做法
void ge…题目
AcWing 868. 筛质数 题解
方法一朴素筛法 及其优化埃氏筛 从2~n枚举 i,再从小到大枚举所有已知的质数 primes[j],筛掉合数 i*primes[j],遇到新的质数就入队 枚举所有小于n的数i,将i的所有倍数筛掉。 筛完后剩下的数就是质数。 朴素做法
void get_primes(int 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/2 n/3 ....n/n n log n大概朴素做法的优化:埃氏筛法。此算法由一个埃及人发明所以叫 埃氏筛法 原理当i不是质数时没必要筛掉它的倍数因为它的吧倍数将会是其它质数的倍数。筛到N时如果N没有被筛掉就说在2~i-1中没有N的约数所以N是质数。 时间是O(n log n)约等于 O(n)和O(n)一个级别 3.补充质数定理1~n当中有 n / logn 个质数 埃氏筛法
void get_primes(int n ){for(int i 2; i n; i ){if(!st[i]) {primes[cnt ] n;//没被筛掉说明是质数for(int j i i; j n; j i)//干掉它的所有倍数st[j] 1;} }
}
时间是O(n log log n)和O(n)一个级别方法二线性筛法求质数 原理 n只会被n的最小质因子筛掉 操作 枚举i:(2~n) i % primes[j] 0 primes[j]一定是i的最小质因子. primes[j]一定是primes[j] * i的最小质因子.i % primes[j] ! 0 由于是从小到大枚举的质数若此时还没枚举到i的任何一个质因子。 说明primes[j]一定小于i的最小质因子。 那么 primes[j] 也一定是primes[j] * i的最小质因子。 这个操作可以保证枚举到i时所有小于等于i的合数都一定会被筛掉。 证明对于任意一个合数x,假设primes[j]是x的最小质因数,i一定会在x之前枚举到x/primes[j],这时x就会被筛掉。 举例 比如n12时,x的最小质因数primes[j] 2 那么i一定会在12之前枚举到n/primes[j] 6,此时就会把2*6 12 n筛掉。 时间数据范围在 107以上的时候,线性筛法比埃氏筛法快一倍。 void get_primes(int n ){for(int i 2; i n; i ){//没被筛掉说明是质数,将这个新的质数加入primes里if(!st[i]) primes[cnt ] i;//从小到大枚举所有已知的质数 primes[j]for(int j 0; primes[j] n / i; j ){ //当质数大于n / i的时候break;//等价于 primes[j] * i n;也就是筛掉所有小于n的合数就可以了//筛掉合数 i*primes[j]st[primes[j] * i] 1; //当这句话发生的时候,primes[j]一定是i的最小质因子//那么用i的最小质因子筛掉i的目的已经达成了,所以跳出循环.if(i % primes[j] 0) break;}}
}代码
#includebits/stdc.h
using namespace std;const int N 1000010;int primes[N], cnt;
bool st[N];void get_primes(int n ){for(int i 2; i n; i ){if(!st[i]) primes[cnt ] i;for(int j 0; primes[j] n / i; j ){st[primes[j] * i] 1;if(i % primes[j] 0) break;}}
}int main(){int n;cin n;get_primes(n);cout cnt endl;return 0;
}
