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.

题意概述

给定$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;
}