#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;

typedef unsigned long long ull;

// 快速乘（模乘），避免 a*b 溢出
ull mod_mul(ull a, ull b, ull m) {
    return (ull)((__int128)a * b % m);
}

// 快速幂取模
ull mod_pow(ull a, ull b, ull m) {
    ull res = 1;
    a %= m;
    while (b) {
        if (b & 1) res = mod_mul(res, a, m);
        a = mod_mul(a, a, m);
        b >>= 1;
    }
    return res;
}

// Miller-Rabin 确定性测试（针对 64 位整数）
bool miller_rabin(ull n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;
    ull d = n - 1;
    int s = 0;
    while (d % 2 == 0) { d /= 2; s++; }
    // 用前 12 个质数作为底数，对 64 位整数足够可靠
    ull bases[] = {2,3,5,7,11,13,17,19,23,29,31,37};
    for (ull a : bases) {
        if (a >= n) continue;
        ull x = mod_pow(a, d, n);
        if (x == 1 || x == n-1) continue;
        bool composite = true;
        for (int i = 0; i < s-1; i++) {
            x = mod_mul(x, x, n);
            if (x == n-1) { composite = false; break; }
        }
        if (composite) return false;
    }
    return true;
}

// 伪随机函数 f(x) = (x^2 + c) % n
ull f(ull x, ull c, ull n) {
    return (mod_mul(x, x, n) + c) % n;
}

// 求最大公因数
ull gcd(ull a, ull b) {
    while (b) {
        ull t = a % b;
        a = b;
        b = t;
    }
    return a;
}

// Pollard Rho 寻找一个非平凡因子
ull pollard_rho(ull n) {
    if (n % 2 == 0) return 2;      // 先检查小因子
    if (n % 3 == 0) return 3;
    // 随机种子（实际中最好用更好的随机数发生器）
    srand(time(0));
    ull c = rand() % (n-1) + 1;    // 随机常数 c，范围 [1, n-1]
    ull x = rand() % (n-2) + 2;    // 随机起点，范围 [2, n-1]
    ull y = x;                     // 快指针初始值
    ull d = 1;
    // Floyd 判圈
    while (d == 1) {
        x = f(x, c, n);            // 慢指针走一步
        y = f(f(y, c, n), c, n);   // 快指针走两步
        d = gcd(x > y ? x - y : y - x, n);  // 计算差值绝对值与 n 的 gcd
    }
    // 如果 d==n，说明因 c 不合适导致循环全等，重新尝试
    if (d == n) return pollard_rho(n);
    return d;
}

// 递归分解质因数
void factor(ull n, vector<ull>& factors) {
    if (n == 1) return;
    if (miller_rabin(n)) {
        factors.push_back(n);
        return;
    }
    ull d = pollard_rho(n);
    factor(d, factors);
    factor(n / d, factors);
}

int main() {
    ull num;
    cout << "请输入一个大于1的整数: ";
    cin >> num;
    if (num <= 1) {
        cout << "输入必须大于1" << endl;
        return 0;
    }
    vector<ull> factors;
    factor(num, factors);
    sort(factors.begin(), factors.end());
    cout << num << " 的质因数分解: ";
    for (size_t i = 0; i < factors.size(); i++) {
        cout << factors[i];
        if (i != factors.size() - 1) cout << " * ";
    }
    cout << endl;
    return 0;
}

import random
import math

def mod_mul(a, b, m):
    """快速乘（Python 直接乘法即可，因为自动大数）"""
    return (a * b) % m

def mod_pow(a, b, m):
    """快速幂取模"""
    res = 1
    a %= m
    while b:
        if b & 1:
            res = mod_mul(res, a, m)
        a = mod_mul(a, a, m)
        b >>= 1
    return res

def miller_rabin(n, k=12):
    """Miller-Rabin 素性测试，k 为测试次数"""
    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
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = mod_pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        composite = True
        for _ in range(s - 1):
            x = mod_mul(x, x, n)
            if x == n - 1:
                composite = False
                break
        if composite:
            return False
    return True

def gcd(a, b):
    """辗转相除法求最大公因数"""
    while b:
        a, b = b, a % b
    return a

def pollard_rho(n):
    """Pollard Rho 找非平凡因子"""
    if n % 2 == 0:
        return 2
    if n % 3 == 0:
        return 3
    # 随机参数
    c = random.randrange(1, n - 1)   # 随机常数 c
    x = random.randrange(2, n - 1)   # 随机起点
    y = x
    d = 1
    # Floyd 判圈
    while d == 1:
        x = (mod_mul(x, x, n) + c) % n          # 慢指针走一步
        y = (mod_mul(y, y, n) + c) % n
        y = (mod_mul(y, y, n) + c) % n          # 快指针走两步
        d = gcd(abs(x - y), n)
    if d == n:  # 失败，重试（更换随机参数）
        return pollard_rho(n)
    return d

def factor(n, factors=None):
    """递归分解 n，结果存入 factors 列表"""
    if factors is None:
        factors = []
    if n == 1:
        return factors
    if miller_rabin(n):
        factors.append(n)
        return factors
    d = pollard_rho(n)
    factor(d, factors)
    factor(n // d, factors)
    return factors

def main():
    try:
        num = int(input("请输入一个大于1的整数: "))
        if num <= 1:
            print("输入必须大于1")
            return
        factors = factor(num, [])
        factors.sort()
        print(f"{num} 的质因数分解: {' * '.join(map(str, factors))}")
    except ValueError:
        print("请输入有效整数")

if __name__ == "__main__":
    main()