給出正整數(shù)n和m，區(qū)間[n,m]內(nèi)的質(zhì)數(shù)有多少個？

1<=n<=m<=10^12,m-n<=10^7;

#include <iostream> #include <cmath> #include <cstring>using namespace std; const int N=1e7+5; typedef long long LL; LL n,m; int check[N]; void Judge(){memset(check,0,sizeof(check));int p,t=sqrt(m+0.5);for(int i=2;i<=t;i++){int q=ceil((double)n/i);if(q<i) p=i*i;else p=i*q;for(;p<=m;p+=i)check[p-n]=1;}int cnt=0;for(int i=0;i<=m-n;i++)if(!check[i]) cnt++;cout<<cnt<<endl;}

區(qū)間[n,m]內(nèi)的“無平方因子”的數(shù)有多少個？

1<=n<=m<=10^12,m-n<=10^7;

代碼如下：

void Judge2() {memset(check,0,sizeof(check));int i,j,p=sqrt(m+0.5);for(i=2;i<=p;i++){for(j=i*i;j<=m;j+=i*i) if(j>=n)check[j-n]=1;}int cnt=0;for(int i=0;i<=m-n;i++)if(!check[i]) cnt++;cout<<cnt<<endl; }

總結(jié)

以上是生活随笔為你收集整理的素数筛选_变形的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。