1842. 搜寻素数

include

using namespace std;
bool isprime(int a)
{
        if(a==2||a==3||a==5) return true;
        else if(a==1||a==4) return false;
        else if(a>=6){
                if(a%6!=1&&a%6!=5) return false;
                else if(a%6==1||a%6==5){
                        for(int i=5;i<=sqrt(a);i+=6){
                                if(a%i==0||a%(i+2)==0) return false;
                        }
                        return true;
                }
        }
}
int main()
{
        int t;cin>>t;
        while(t--){
                int n;cin>>n;
                if(isprime(n)) cout<<n<<endl;
                else{
                        for(int i=1;;i++){
                                if(isprime(n+i)&&!isprime(n-i)) {cout<<n+i<<endl;break;}
                                else if(!isprime(n+i)&&isprime(n-i)) {cout<<n-i<<endl;break;}
                                else if(isprime(n+i)&&isprime(n-i)){cout<<n-i<<endl;break;}
                        }
                }
        }
}

include

include

include

using namespace std;
const int MAX = 1000002;
bool mask[MAX];
int search(vector&, int);
int main(void)
{
mask[1] = true;
for (int i = 2; i * i < MAX; i++)
if (!mask[i])
for (int j = 2 * i; j < MAX; j += i)
mask[j] = true;
vector prime;
for (int i = 1; i < MAX; i++)
if (!mask[i])
prime.push_back(i);
int cnt;
cin >> cnt;
while (cnt–)
{
int n;
cin >> n;
int ans = search(prime,n);
cout << ans << endl;
}
return 0;
}
int search(vector& p, int tar)
{
int left = 0, right = p.size() - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (p[mid] == tar)
return p[mid];
else if (p[mid] < tar)
left = mid + 1;
else if (p[mid] > tar)
right = mid - 1;
}
if (!left)
return p[left];
else if (right == p.size() - 1)
return p[right];
else
return abs(p[right] - tar) <= abs(p[left] - tar) ? p[right] : p[left];
}

说好了的非负整数的