题目概述
Nearly prime number is an integer positive number for which it is possible to find such primes $P_1$ and $P_2$ that given number is equal to $P_1 \times P_2$. There is given a sequence on $N$ integer positive numbers, you are to write a program that prints “Yes” if given number is nearly prime and “No” otherwise.
题意概述
给定$N$个数$a_i$,分别判断它们是否仅由两个质数相乘得到。
数据范围:$1 \le N \le 10, \; 1 \le a_i \le 10^9$。
算法分析
可以用Miller-Rabin算法快速判断一个数是否是质数。
Miller-Rabin基于以下几个事实:
- 费马小定理:对于素数$p$和任意整数$a$,有$a^p \equiv a \pmod p$。反之,满足$a^p \equiv a \pmod p$,$p$也几乎一定是素数。
- 伪素数:如果$n$是一个正整数,且存在和$n$互素的正整数$a$满足$a^{n-1} \equiv 1 \pmod n$,那么$n$是基于$a$的伪素数。如果一个数是伪素数,那么它几乎肯定是素数。
- 二次探测定理:如果$p$是奇素数,则$x^2 \equiv 1 \pmod p$的解为$x \equiv \pm 1 \pmod p$。
代码
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define int long long #define random(x) ((1ll * rand() << 30 ^ 1ll * rand() << 15 ^ rand()) % (x) + 1) using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); } template <typename T> inline IOManager operator > (T &x) { read(x); return *this; } template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); } inline void write(char c) { putchar(c); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } template <typename T> inline IOManager operator < (T x) { write(x); return *this; } } io; struct Solver { private: int n; void input() { io > n; } int multiple(int a, int b, int mod) { int ret = 0; a %= mod; while (b) { b & 1 && ((ret += a) %= mod), (a <<= 1) %= mod, b >>= 1; } return ret; } int power(int a, int b, int mod) { int ret = 1; a %= mod; while (b) { b & 1 && ((ret *= a) %= mod), (a *= a) %= mod, b >>= 1; } return ret; } bool is_prime(int n) { if (n == 2) return true; if (n < 2 || ! (n & 1)) return false; int c = 0, p = n - 1, cnt = 30; while (! (p & 1)) ++ c, p >>= 1; while (cnt --) { int a = random(n - 1), x = power(a, p, n); for (int i = 0; i < c; ++ i) { int y = multiple(x, x, n); if (y == 1 && x != 1 && x != n - 1) return false; x = y; } if (x != 1) return false; } return true; } void process() { int a; io > a; int q = sqrt(a); for (int i = 2; i <= q; ++ i) if (! (a % i) && is_prime(i) && is_prime(a / i)) { io < (char *) "Yes\n"; return; } io < (char *) "No\n"; } public: void solve() { input(); while (n --) process(); } } solver; signed main() { solver.solve(); return 0; }