多组测试数据，每组测试数据第一行输入一个正整数n（0< n < 10^9）。
每组测试数据，若n为素数，那么输出“YES”，否则输出“NO”。（引号不输出）
?
思路：由于n非常的大，打表nlogn也不行，我们换一种思路，我们不打10^9，我们只打出它的开平方10^5就差不多了，找出小于10^5以内的素数，然后我们判定n的时候再用
普通素数判别法判定就行
?
?
#include#include #include #include #include #include using namespace std; #define LL long long const double eps = 1e-6; const int INF = 10000000; int n, m , k; const int maxn = 60001; bool ispri[maxn]; int pri[maxn]; void is() { int cnt = 0; memset(ispri , true , sizeof(ispri)); ispri[1] = 0; for(LL i = 2 ; i < maxn ; i ++) { if(ispri[i]) { pri[++ cnt] = i; for(LL j = i * 2 ; j < maxn ; j += i) ispri[j] = false; } } } bool isp(int n) { int m = sqrt(n); for(int i = 1 ; pri[i] <= m ; i ++) if(n % pri[i] == 0) return false; return true; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int n; is(); while(~scanf("%d",&n)) { if(n == 0 || n == 1) { printf("NO\n"); continue; } if(isp(n)) { printf("YES\n"); } else { printf("NO\n"); } } }
?