#include <iostream>
#include <vector>
using namespace std;

const int lim = 1e6;

int n;
vector<int> p(lim + 1, 1);

void sieve() {
    p[0] = p[1] = 0;
    for(int i = 2; i * i <= lim; ++i) {
        if(p[i]) {
            for(int j = i * i; j <= lim; j += i) p[j] = 0;
        }
    }
}

int main() {
    sieve();

    cin >> n;
    cout << (p[n] ? "YES" : "NO");
}

*Đây là cách tối ưu nhất mình nghĩ ra (tìm ước (chạy tới $\sqrt{n}$))

#include <bits/stdc++.h>
using namespace std;
long long n;
int main()
{
    cin >> n;
    bool kt=true;
    for (long long i=2; i<=sqrt(n); i++)
        if (n%i==0)
        {
            kt=false;
            break;
        }
    if (kt==true)
        cout << n << " la so nguyen to";
    else
        cout << n << " khong la so nguyen to";
}