秦皇岛市 网站建设,深圳网站建设有免费的吗,iis端口相同不同网站建设,手机模拟装修app正题 题目大意
求l∼rl\sim rl∼r这个区间素数或两个素数的乘积的数个数 解题思路
在欧式筛的时候判断j是不是素数#xff0c;是就标记就行了。 code
#pragma GCC optimize(2)
#includecstdio
#define N 10000000
#define ll int
using namespace std;
ll prime[N]…正题 题目大意
求l∼rl\sim rl∼r这个区间素数或两个素数的乘积的数个数 解题思路
在欧式筛的时候判断j是不是素数是就标记就行了。 code
#pragma GCC optimize(2)
#includecstdio
#define N 10000000
#define ll int
using namespace std;
ll prime[N],s[N*2],l,r,q,cnt;
bool v[N10];
ll read(){int x0,flag1;char chgetchar();while(ch0||ch9){if(ch-)flag-1;chgetchar();}while(ch0ch9){xx*10ch-0;chgetchar();}return x*flag;
}
void write(ll x)
{if(x9) write(x/10);putchar(x%1048);return;
}
void primes()
{for(ll i2;iN;i)if(!v[i]){prime[cnt]i;s[i]1;//素数也标记for(ll j2;i*jN;j){if(!v[j]ji)//是素数的乘积s[i*j]1;v[i*j]true;}}
}
int main()
{primes();for(ll i1;iN;i)s[i]s[i-1];qread();for(ll i1;iq;i){lread();rread();write(s[r]-s[l-1]);puts();}
}
