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.