Check số nguyên tố - Nhập n, kiểm tra số đó có phải số nguyên tố hay không `2<=n<=10^90` - Time ; 1.0s - Python : cấm dùng print(), sàng, 0.6s - Pascal : cấm dùng for, while - C/C++ : cấm for, while - Còn lại thì được phép : Prolog, F#

Định lý:

`**` Nếu `p` là số nguyên tố thì `a^{p-1} -1` là bội của `p` với mọi `p`.

$\\$

Code dưới dây có độ phức tạp là O(klogn).

Code tham khảo:

from info import processInfo
from math import gcd
from random import randint
import sys

def prime(n, k):
    if (n <= 1 or n == 4): return False
    if (n <= 3): return True
    
    for _ in range(k):
        a = randint(2, n-2)
        if (pow(a, n-1, n) != 1):
            return False
            
    return True
    
def main():
    k = 100
    sys.stdout.write(str(prime(n, k))+'\n')
    
n = int(input())

processInfo(main)

$\\$
$\\$
$\color{#ffd710}{\texttt{\{}} \color{#8655d6}{\texttt{\{}}\ \ \color{#8cdcda}{\text{Daoanhviet96}}\ \ \color{#8655d6}{\texttt{\}}} \color{#ffd710}{\texttt{\}}}$