poj 1811（随机化素数测试+素因子分解，未解决）

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
ll witness(ll a, ll n){
    int x, d=1, i = ceil(log(n - 1.0) / log(2.0)) - 1;
    for ( ; i >= 0; i--) {
        x = d; d = (d * d) % n;
        if (d==1 && x!=1 && x!=n-1) return 1;
        if (((n-1) & (1<<i)) > 0) d = (d * a) % n;
    }
    return (d == 1 ? 0 : 1);
}
ll miller(ll n, ll s = 50){
    if (n == 2) return 1;
    if ((n % 2) == 0) return 0;
    int j, a;
    for (j = 0; j < s; j++) {
        a = rand() * (n-2) / RAND_MAX + 1;
        // rand()只能随机产生[0, RAND_MAX)内的整数
        // 而且这个RAND_MAX只有32768直接%n的话永远也产生不了
        // [RAND-MAX, n)之间的数
        if (witness(a, n)) return 0;
    }
    return 1;
}
int main(){
    int t;
    ll n;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        if(miller(n))printf("Prime\n");
        else printf("%lld\n",n);
    }
    bool flag = miller(n);
    return 0;
}