#include <iostream>
using namespace std;

typedef unsigned long long ull;  // 定义无符号长长整型为ull，方便输入大数

// 快速幂取模：计算 (a的b次方) % m，使用二进制分解加速
ull mod_pow(ull a, ull b, ull m) {
    ull result = 1;          // 存放最终结果，初始为1
    a %= m;                  // 先让a模一下m，防止太大
    while (b > 0) {
        if (b & 1) {          // 如果b当前二进制位是1
            result = (__int128)result * a % m;  // 乘上a，并取模（用__int128防止乘法溢出）
        }
        a = (__int128)a * a % m;  // a自己平方，并取模
        b >>= 1;                 // b右移一位，相当于除2
    }
    return result;
}

// 单次Miller-Rabin测试，用基a检测n
bool miller_rabin_test(ull n, ull a) {
    if (a % n == 0) return true;   // 如果a是n的倍数，跳过（这种情况不会暴露问题）

    // 将 n-1 分解为 d * 2^s
    ull d = n - 1;
    int s = 0;
    while (d % 2 == 0) {
        d /= 2;
        s++;
    }

    ull x = mod_pow(a, d, n);      // 计算 a^d mod n
    if (x == 1 || x == n - 1) return true;  // 通过第一关

    for (int i = 0; i < s - 1; i++) {
        x = (__int128)x * x % n;   // 平方取模
        if (x == n - 1) return true;      // 出现了 -1，通过
        if (x == 1) return false;  // 出现了1以外的平方根，n一定是合数！
    }
    return false;  // 循环结束都没出现 -1，合数
}

// 判断n是否为质数（确定性基组，适用于n < 2^64）
bool is_prime(ull n) {
    if (n < 2) return false;        // 小于2不是质数
    if (n == 2 || n == 3) return true;  // 2和3是质数
    if (n % 2 == 0) return false;   // 偶数（除2外）不是质数

    // 确定性基组：对于 n < 2^64，这些基就足够了
    ull bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for (ull a : bases) {
        if (a >= n) break;          // 如果基>=n，跳过（因为没意义）
        if (!miller_rabin_test(n, a)) {
            return false;           // 有一个基没通过，就是合数
        }
    }
    return true;  // 所有基都通过，n被认为是质数
}

int main() {
    ull num;
    cout << "请输入一个整数（支持到unsigned long long）: ";
    cin >> num;
    if (is_prime(num)) {
        cout << num << " 是质数。" << endl;
    } else {
        cout << num << " 不是质数。" << endl;
    }
    return 0;
}

import random

def mod_pow(a, b, m):
    """快速幂取模：计算 a^b mod m，用于大数"""
    result = 1
    a %= m
    while b > 0:
        if b & 1:          # 如果b当前二进制位是1
            result = (result * a) % m
        a = (a * a) % m
        b >>= 1
    return result

def miller_rabin_test(n, a):
    """单次Miller-Rabin测试，用基a检测n"""
    if a % n == 0:
        return True       # 跳过倍数情况
    # 分解 n-1 = d * 2^s
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    x = mod_pow(a, d, n)
    if x == 1 or x == n - 1:
        return True
    for _ in range(s - 1):
        x = (x * x) % n
        if x == n - 1:
            return True
        if x == 1:
            return False   # 二次探测发现非平凡平方根
    return False

def is_prime(n, k=12):
    """
    Miller-Rabin素性测试
    参数:
        n: 待测整数（支持任意大）
        k: 测试循环次数，默认12次，错误概率极低
    对于小于2^64的数，可以用确定性基组（上面C++实现）；这里用随机，更通用。
    """
    if n < 2:
        return False
    # 先检查小质数，快速排除
    small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for p in small_primes:
        if n % p == 0:
            return n == p   # 如果能被小质数整除，只有等于它本身才是质数
    # 随机测试k次
    for _ in range(k):
        a = random.randrange(2, n - 1)   # 随机选一个2到n-2之间的基
        if not miller_rabin_test(n, a):
            return False
    return True   # 所有测试通过，基本确定是质数

def main():
    try:
        num = int(input("请输入一个整数: "))
        if is_prime(num):
            print(f"{num} 是质数。")
        else:
            print(f"{num} 不是质数。")
    except ValueError:
        print("请输入有效整数")

if __name__ == "__main__":
    main()