Mật khẩu bạn Nam sử dụng để truy cập vào trang web học trực tuyến là một số nguyên tố có tổng các chữ số là một số chẵn. Thay vì ghi lại mật khẩu này, bạn Nam chỉ ghi lại một số nguyên 𝑛 có giá trị nhỏ hơn mật khẩu. Yêu cầu: Cho biết số nguyên 𝑛, hãy tìm mật khẩu có giá trị nhỏ nhất trong số các mật khẩu bạn Nam có thể sử dụng. Dữ liệu vào: Đọc từ bàn phím số nguyên 𝑛; Kết quả: Ghi ra màn hình mật khẩu tìm được. Ví dụ: NTO.INP NTO.OUT 20 Mat khau la: 31 1001 Mat khau la: 1009 HAPPY NEW YEAR

- Cách 1: 6k +- 1

uses crt;
type int = longint;
var n: int;

function prime(x: int): boolean;
var i: int;
begin
    if x <= 1 then exit(false);
    if x mod 2 = 0 then exit(x = 2);
    if x mod 3 = 0 then exit(x = 3);
    
    i:=5;
    while i * i <= x do begin
        if (x mod i = 0) or (x mod (i + 2) = 0) then
            exit(false);
        inc(i, 6);
    end;
    exit(true);
end;

function check(x: int): boolean;
var r: int;
begin
    if not prime(x) then exit(false);
    r:=0;
    while x > 0 do begin
        inc(r, x mod 10);
        x:=x div 10;
    end;
    exit(r and 1 = 0);
end;

begin
    readln(n); inc(n);
    while check(n) = false do inc(n);
    writeln(n);
end.

- Cách 2: miller - rabin

uses crt;
type int = int64;
var n: int;

var ck_prime: array of int = (2, 7, 61);

function pow(a, n, m: int): int;
var res: int;
begin
    res:=1;
    while n > 0 do begin
        if n and 1 = 1 then res:=(res * a) mod m;
        a:=(a * a) mod m;
        n:=n shr 1;
    end;
    exit(res);
end;

function check(a, s, d, n: int): boolean;
var p: int;
begin
    if n = a then exit(true);
    p:=pow(a, d, n);
    if p = 1 then exit(true);
    
    while s > 0 do begin
        dec(s);
        if p = n - 1 then exit(true);
        p:=(p * p) mod n;
    end;
    exit(false);
end;

function prime(x: int): boolean;
var i, d, s: int;
begin
    if x <= 1 then exit(false);
    if x mod 2 = 0 then exit(x = 2);
    if x mod 3 = 0 then exit(x = 3);
    
    d:=x - 1; s:=0;
    while d and 1 = 0 do begin
        inc(s);
        d:=d shr 1;
    end;
    for i:=0 to 2 do 
        if check(ck_prime[i], s, d, x) = false then exit(false);
    exit(true);
end;

function check(x: int): boolean;
var r: int;
begin
    if not prime(x) then exit(false);
    r:=0;
    while x > 0 do begin
        inc(r, x mod 10);
        x:=x div 10;
    end;
    exit(r and 1 = 0);
end;

begin
    readln(n); inc(n);
    while check(n) = false do inc(n);
    writeln(n);
end.