View difference between Paste ID: BsgpwtJg and JpCKEak1
SHOW: | | - or go back to the newest paste.
1
/* Courtesy: TopCoder Algorithm Tutorials on Primality Testing: Non Deterministic Algorithms */
2
 
3-
//#include<iostream>
3+
#include<iostream>
4
#include<cstdio>
5
#include<algorithm>
6
#include<cstring>
7
#include<cstdlib>
8
#include<cctype>
9
#include<cmath>
10
#include<climits>
11
#include<vector>
12
#include<iterator>
13
#include<set>
14
#include<bitset>
15
#include<ctime>
16
 
17
#define fr(i,a,b) for(int i=a; i<b; i++)
18
#define s(a) scanf("%d", &a)
19
#define sl(a) scanf("%lld", &a)
20
#define p(a) printf("%d\n", a)
21
#define w(t) while(t--)
22
#define pb push_back
23
#define CLR(a) memset(a, 0, sizeof(a))
24
 
25
using namespace std;
26
 
27
typedef long long int lli;
28
typedef vector<int> VI;
29
typedef vector<string> VS;
30
 
31
lli mulmod(lli a, lli b, lli c) {
32
	lli x = 0, y = a%c; 
33
	while(b > 0) {
34
		if(b%2)	x = (x+y)%c;
35
		y = (y<<1)%c; 
36
		b >>= 1;
37
	} 
38
	return x%c; 
39
}
40
 
41
lli modulo(lli a, lli b, lli c) {
42
	lli x=1, y=a;
43
	while(b > 0) {
44
		if(b%2)	x = mulmod(x, y, c);
45
		//x=(x*y)%c;
46
		y = mulmod(y, y, c);
47
		//y = (y*y)%c;
48
		b >>= 1;
49
	} 
50
	return x%c; 
51
}
52
 
53
bool Miller(lli p, int iteration) {
54
	if(p<2)					return false;
55-
	if(p!=2 && p%2==0)		return false;
55+
	if(p!=2 && p%2==0)			return false;
56
	lli s=p-1; 
57
	while(s%2==0)	s >>= 1;
58
	fr(i,0,iteration) {
59
		lli a = rand()%(p-1) + 1, temp = s; 
60
		lli mod = modulo(a, temp, p); 
61
		while(temp != p-1 && mod != 1 && mod != p-1) {
62
			mod = mulmod(mod, mod, p); 
63
			temp <<= 1; 
64
		} 
65
		if(mod != p-1 && temp%2 == 0)	return false;
66
	} 
67
	return true; 
68
}
69
 
70
int main() {
71
	int t;
72
	s(t);
73
	w(t) {
74
		lli n, ans;
75
		sl(n);
76
		bool isPrime = false;
77
		while(Miller(n,2) == false)	--n;
78
		printf("%lld\n", n);
79
	}
80
	return 0;
81
}