Editorial for Lại là số nguyên tố
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include <iostream> #include <algorithm> #include <cstdio> using namespace std; unsigned long long power(unsigned long long x,unsigned long long y,unsigned long long z) { if (!y) return 1; unsigned long long r=power(x,y/2,z); r=r*r%z; if (y%2) r=r*x%z; return r; } int probablyPrime(unsigned long long n,int iteration) { if (n<3) return n==2; if (n%2==0) return 0; unsigned long long s=n-1,p=0; while (s%2==0) s/=2, p++; while (iteration--) { unsigned long long x=power(rand()%(n-1)+1,s,n); for (int i=1;i<=p;i++) { unsigned long long xx=x; x=x*x%n; if (x==1 && xx!=1 && xx!=n-1) return 0; } if (x!=1) return 0; } return 1; } int main() { int test; cin >> test; while (test--) { unsigned long long n; cin >> n; n--; while (!probablyPrime(n,10)) n--; cout << n << endl; } }
Code mẫu của happyboy99x
#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; }
Code mẫu của ladpro98
const fi=''; function powmod(i,j,k:longword):qword; var t:qword; begin if j=1 then exit(i mod k); t:=powmod(i,j div 2,k) mod k; if odd(j) then exit((((t*i) mod k)*t) mod k); exit((t*t) mod k); end; function rabinmiller(p:longword):boolean; var temp,s,a:int64; modul:qword; i:longint; begin if (p<2) then exit(false); if (p <> 2) and (p mod 2 = 0) then exit(false); s:=p-1; while s mod 2 = 0 do s:=s div 2; for i:=1 to 3 do begin a:=random(p-3)+2; temp:=s; modul:=powmod(a,temp,p); while (temp<>p-1) and (modul<>1) and (modul<>p-1) do begin modul:=((modul mod p)*(modul mod p)) mod p; temp:=temp*2; end; if (modul<>p-1) and (temp mod 2 = 0) then exit(false); end; exit(true); end; procedure input; var i,t:longint; j:int64; inp:text; begin randomize; assign(inp,fi); reset(inp); readln(inp,t); for i:=1 to t do begin readln(inp,j); dec(j); while j>=2 do begin if rabinmiller(j) then begin writeln(j); break; end; dec(j); end; end; close(inp); end; begin input; end.
Code mẫu của RR
{$R+,Q+} {$Mode objFPC} const FINP = ''; FOUT = ''; k = 2; var f1,f2 : text; n : qword; test : longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; //Miller-rabin test by Pham Quang Vu //power = (a^q) mod n function power(a,q,n:qword):qword; inline; var u:qword; begin if q=1 then exit(a mod n); if q=0 then exit(1); u:=power(a,q shr 1,n); if q and 1=1 then exit( ((u*u) mod n*a) mod n ) else exit( (u*u) mod n ); end; function millertest(n,a,q,t:qword):boolean; inline; var pre,c:qword; i:longint; begin c:=power(a,q,n); pre:=n-1; for i:=0 to t do begin if c=1 then exit(pre=n-1); pre:=c; c:=(c*c) mod n; end; exit(false); end; //n = 2^t * q procedure cal(n:qword; var q,t:qword); inline; begin t:=0; while n and 1=0 do begin inc(t); n:=n shr 1; end; q:=n; end; function prime(n:qword):boolean; inline; var i:longint; a,q,t:qword; begin cal(n-1,q,t); for i:=1 to k do begin a:=random(n-1)+1; if not millertest(n,a,q,t) then exit(false); end; exit(true); end; //End of Miller-rabin test by Pham Quang Vu procedure solve; begin n-=1; if n and 1=0 then n-=1; repeat if (n=3) or (n=5) or (n=7) then begin writeln(f2,n); exit; end; if (n mod 5>0) and (n mod 7>0) then if (n mod 3>0) and prime(n) then begin writeln(f2,n); exit; end; n-=2; until false; end; begin openF; readln(f1,test); for test:=1 to test do begin readln(f1,n); if n=3 then writeln(f2,2) else solve; end; closeF; end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> #include <stdlib.h> #include <math.h> #include <algorithm> bool isPrime(int n) { if (n<2) return false; // optional for (int i=2; i*i<=n; ++i) if (n%i==0) return false; return true; } unsigned long long power(unsigned long long a, unsigned long long d,unsigned long long n) { if(d==1) return a%n; else { unsigned long long k = power(a,d/2,n); if(d%2==0) return k*k%n; else return ((k*k)%n*a)%n; } } bool rabinMiller(unsigned long long n, int k) { if (n<=50) return isPrime(n); unsigned long long d=n-1, s=0; while (d%2==0) {++s; d/=2;} for (int i=1; i<=k; ++i) { unsigned long long a = rand()%(n-2)+2; unsigned long long x = power(a,d,n); if (x == 1 || x == n-1) continue; for (int r=1; r<s; ++r) { x=(unsigned long long)(x*x) % n; if (x==1) return false; if (x==n-1) break; } if (x!=n-1) return false; } return true; } int main() { int test; unsigned long long n; scanf("%d",&test); for(int i = 1;i<=test;i++) { scanf("%lld",&n); n--; while(true) { if(rabinMiller(n,20)) { printf("%lld\n",n); break; } n--; } } // getch(); }
Code mẫu của ll931110
{$MODE DELPHI} Program PAGAIN; Const input = ''; output = ''; a: array[1..3] of integer = (2,7,61); Var i,t: integer; n: qword; fi,fo: text; Procedure openfile; Begin Assign(fi, input); Reset(fi); Assign(fo, output); Rewrite(fo); End; Function power(x,p,k: qword): qword; Var u: qword; Begin If p = 0 then exit(1); u:= power(x,p div 2,k); If odd(p) then power:= ((u * u) mod k * x) mod k else power:= (u * u) mod k; End; Function RabinMiller(k: qword): boolean; Var i,j: integer; st,test,bs,p2: qword; ch: boolean; Begin bs:= k - 1; p2:= 0; While bs mod 2 = 0 do Begin bs:= bs div 2; inc(p2); End; RabinMiller:= false; ch:= true; For i:= 1 to 3 do if k >= a[i] then Begin ch:= false; st:= power(a[i],bs,k); test:= st; If (test = 1) or (test = k - 1) then Begin ch:= true; break; End; For j:= 1 to p2 - 1 do Begin test:= (test * test) mod k; If (test = 1) or (test = k - 1) then Begin ch:= true; break; End; End; If not ch then exit(false); End; RabinMiller:= true; End; Procedure solve; Var k: qword; Begin Readln(fi, n); If n = 3 then Begin writeln(fo, 2); exit; End; k:= n; dec(k); If not odd(k) then dec(k); While not RabinMiller(k) do k:= k - 2; Writeln(fo, k); End; Procedure closefile; Begin Close(fo); Close(fi); End; Begin openfile; Readln(fi, t); For i:= 1 to t do solve; closefile; End.
Comments