PAGAIN - Prime Again

Tác giả: happyboy99x

Ngôn ngữ: C++

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef unsigned long long LL;

#define sz(a) (int((a).size()))
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N

LL powmod(LL a, LL b, LL n) {
	if(b == 0) return 1;
	LL res = powmod(a, b/2, n);
	return (b%2==1) ? (((res*res)%n)*a)%n : ((res*res)%n);
}

bool MillerTest(LL n, LL s, LL m) {
	LL a = (LL) rand() % (n-2) + 2, b = powmod(a, m, n);
	LL pre = n-1;
	repd(i,s+1) {
		if(b == 1) return pre == n-1;
		pre = b; b = (b*b) % n;
	}
	return 0;
}

bool prime(LL n) {
	if(n == 2) return 1;
	if(n % 2 == 0 || n < 2) return 0;
	LL s = 63 - __builtin_clzll((n-1)&(1-n)), m = (n-1) >> s;
	for(int k=0; k<30; ++k) 
		if(!MillerTest(n, s, m)) return 0;
	return 1;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen( "input.txt", "r", stdin );
	//freopen( "output.txt", "w", stdout );
#endif
	int tc; LL n; srand(time(NULL));
	scanf("%d",&tc);
	while(tc--) {
		scanf("%llu",&n);
		while(!prime(--n));
		printf("%llu\n", n);
	}
	return 0;
}

Download