# Nearly Prime Numbers

## 题目概述

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.

## 算法分析

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;
}


418 I'm a teapot