Hướng dẫn giải của Lại là số nguyên tố
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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.
Bình luận