Код
#include "iostream"
#include "vector"
using namespace std;
int f(int n) {
vector<char> prime (n+1, true);
prime[0] = prime[1] = false;
for (int i=2; i<=n; ++i)
if (prime[i])
for (int j=i*i; j<=n; j+=i)
prime[j] = false;
return prime[n];}
int main () {
int n;
cin >> n;
int *a=new int [n];
for (int i=0;i<n;i++) {cin >> a[i];
if (f(a[i])) cout << "YES" << endl; else cout << "NO" << endl;}
return 0;}
#include "vector"
using namespace std;
int f(int n) {
vector<char> prime (n+1, true);
prime[0] = prime[1] = false;
for (int i=2; i<=n; ++i)
if (prime[i])
for (int j=i*i; j<=n; j+=i)
prime[j] = false;
return prime[n];}
int main () {
int n;
cin >> n;
int *a=new int [n];
for (int i=0;i<n;i++) {cin >> a[i];
if (f(a[i])) cout << "YES" << endl; else cout << "NO" << endl;}
return 0;}
Числа в диапазоне от 1 до 10^9. По времени работает нормально, но, я так понимаю, на слишком больших числах использует много памяти. Как можно переделать?