#include <iostream> #include <cmath> // 用于sqrt函数 using namespace std; // 判断是否为素数的函数 bool isPrime(int n) { // 题目保证n≥3，无需处理n<2的情况 // 先排除偶数（3以上的偶数都不是素数） if (n % 2 == 0) { return false; } // 只需要检查从3开始的奇数，直到√n int sqrt_n = sqrt(n); for (int i = 3; i <= sqrt_n; i += 2) { if (n % i == 0) { return false; // 能被整除，不是素数 } } return true; // 不能被任何数整除，是素数 } int main() { int n; // 读取输入的正整数 cin >> n; // 判断并输出结果 if (isPrime(n)) { cout << "prime" << endl; } else { cout << "not prime" << endl; } return 0; }