品牌网站建设优化公司,服装外贸网站建设,免费的短视频app有哪些,广告营销文案题意#xff1a; 给定区间L#xff0c;R。 计算区间中素数个数。 2 L,R 2147483647, R-L 1000000。 思路#xff1a; 素数区间筛 先筛(2-sqrt(r))。 再用(2-sqrt(r))中的素数筛(l-r)。 代码: 1.自己写的区间筛#xff0c;将筛2-sqrt#xff08;r) 分开了。…题意 给定区间LR。 计算区间中素数个数。 2 L,R 2147483647, R-L 1000000。 思路 素数区间筛 先筛(2-sqrt(r))。 再用(2-sqrt(r))中的素数筛(l-r)。 代码: 1.自己写的区间筛将筛2-sqrtr) 分开了。 #include iostream
#include string
#include queue
#include memory.h
#include math.h
using namespace std;
typedef long long LL;
const int MAXN 1000010;
int isPrimersmall[MAXN];
int isPrimer[MAXN];int main()
{LL l,r;scanf(%lld%lld,l,r);isPrimersmall[0] 1;isPrimersmall[1] 1;int x sqrt(r);for (int i 2;ix;i){if (isPrimersmall[i] 0){for (int j i * i; j x; j i)isPrimersmall[j] 1;}}for (int i 2;ix;i){if (isPrimersmall[i] 0){for (int j (int)((l (i-1))/ i) * i;j r; j i){if (j ! i)isPrimer[j-l] 1;}}}int sum 0;for (int i 0;ir-l;i){if (isPrimer[i] 0)sum;}printf(%d\n,sum);return 0;
}2.将筛(2-sqrt(r))和(l-r)放在一起筛。 #include iostream
#include string
#include queue
#include memory.h
#include math.h
using namespace std;
typedef long long LL;
const int MAXN 1000010;
int isPrimersmall[MAXN];
int isPrimer[MAXN];int segement_sieve(LL a,LL b)
{for (LL i 0;i*i b;i)isPrimersmall[i] 1;for (LL i 0;i b-a;i)isPrimer[i] 1;for (LL i 2;i*i b;i){if (isPrimersmall[i]){for (LL j i*2;j*j b;ji)isPrimersmall[j] 0;for (LL j max(2LL,(ai-1)/i) * i;j b ;ji)isPrimer[j-a] 0;}}int sum 0;for (int i 0;i b-a;i)if (isPrimer[i])sum;return sum;
}int main()
{LL a,b;scanf(%lld%lld,a,b);printf(%d\n,segement_sieve(a,b));return 0;
}转载于:https://www.cnblogs.com/YDDDD/p/10266165.html
