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 | } |