招商网站的建设目的,wordpress 模板修改,台州做网站优化,o2o网站开发相关技术给定整数a和b#xff0c;请问区间[a,b)内有多少个素数#xff1f; ab10^12 b-a10^6 因为b以内合数的最小质因数一定不超过sqrt(b),如果有sqrt(b)以内的素数表的话#xff0c;就可以把筛选法用在[a,b)上了,先分别做好[2,sqrt(b))的表和[a,b)的表#xff0c;然后… 给定整数a和b请问区间[a,b)内有多少个素数 ab10^12 b-a10^6 因为b以内合数的最小质因数一定不超过sqrt(b),如果有sqrt(b)以内的素数表的话就可以把筛选法用在[a,b)上了,先分别做好[2,sqrt(b))的表和[a,b)的表然后从[2,sqrt(b))的表中筛得素数的同时也将其倍数从[a,b)的表中划去最后剩下的就是区间[a,b)内的素数了。 有的时候需要求出某个特定区间的素数但是数可能很大数组也开不小所以需要进行下标偏移这样才可以使用筛选法。 1 #include cstdio2 #include cstring3 #include algorithm4 using namespace std;5 typedef long long ll;6 const int maxn 1000005;7 bool is_prime[maxn];8 bool is_prime_small[maxn];9 ll prime[maxn];
10 ll prime_num0;
11
12 //对区间[a,b)内的整数执行筛法is_prime[i-a]true --- 表示i是素数 注意这里下标偏移了a所以从0开始。
13 void segment_sieve(ll a,ll b) {
14 for(ll i0;i*ib;i) is_prime_small[i]true; //对[2,sqrt(b))的初始化全为质数
15 for(ll i0;ib-a;i) is_prime[i]true; //对下标偏移后的[a,b)进行初始化
16
17 for(ll i2;i*ib;i) {
18 if(is_prime_small[i]) {
19 for(ll j2*i;j*jb;ji) is_prime_small[j]false; //筛选[2,sqrt(b));
20 //(ai-1)/i得到最接近a的i的倍数最低是i的2倍然后筛选
21 for(ll jmax(2LL,(ai-1)/i)*i;jb;ji) is_prime[j-a]false;
22 }
23 }
24 for(ll i0;ib-a;i) //统计个数
25 if(is_prime[i]) prime[prime_num]ia;
26 }
27
28 int main()
29 {
30 ll a,b;
31 while(~scanf(%lld%lld,a,b))
32 {
33 prime_num0;
34 memset(prime,0,sizeof(prime));
35 segment_sieve(a,b);
36 //for(ll i0;iprime_num;i) printf(%lld\n,prime[i]);
37 printf(%lld\n,prime_num);
38 }
39 return 0;
40 } 转载于:https://www.cnblogs.com/nowandforever/p/4515612.html
