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.

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.