[模板] [洛谷] 線性篩素數  P3383 P1865

P3383 線性篩素數

#include <iostream>
using namespace std;
const int MAXN = 1e7   10;
int check[MAXN] = {0};
int prime[MAXN] = {0};
int pos = 0;
int flag;
void initprime(int len)
{
for(int i = 2; i < len; i  )
{
if(!check[i])
prime[pos  ] = i;
for(int j = 0; j < len && i * prime[j] < len; j  )
{
check[i * prime[j] ] = 1;
if(i % prime[j] == 0)
break;
}
}
}
bool bserch(int x)
{
int fst = 0, lst = pos - 1, mid;
while(fst <= lst)
{
mid = (fst   lst) / 2;
if(prime[mid] > x)
lst = mid - 1;
else if(prime[mid] < x)
fst = mid   1;
else
return true;
}
return false;
} 
int main()
{
int len, t;
cin>>len>>t;
initprime(len   1);
while(t--)
{
int tmp;
cin>>tmp;
if(bserch(tmp))
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
}
return 0;
}

 

 

P1865 

線篩 二分尋下屆

效率非常高

#include <iostream>
using namespace std;
const int MAXN = 1e7   10;
int check[MAXN] = {0};
int prime[MAXN] = {0};
int pos = 0;
int flag;
void initprime(int len)
{
for(int i = 2; i < len; i  )
{
if(!check[i])
prime[pos  ] = i;
for(int j = 0; j < len && i * prime[j] < len; j  )
{
check[i * prime[j] ] = 1;
if(i % prime[j] == 0)
break;
}
}
}
int bserch(int x)
{
int fst = 0, lst = pos - 1, mid;
while(fst < lst)
{
mid = (fst   lst) / 2;
if(prime[mid] >= x)
lst = mid;
else
fst = mid   1;
}
return fst;
} 
int main()
{
int len, t;
cin>>t>>len;
initprime(len   10);
while(t--)
{
int a, b;
cin>>a>>b;
if(a < 1 || b > len)
{
cout<<"Crossing the line"<<endl;
}
else
{
int ans = 0;
int p, q;
p = bserch(a);
q = bserch(b);
ans = q - p;
if(prime[q] <= b)
ans  ;
cout<<ans<<endl;
}
}
return 0;
}