Số nguyên tố

View as PDF

Submit solution

Points: 1.23 (partial)
Time limit: 0.38s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Số nguyên tố là số chỉ chia hết cho ~1~ và chính nó. Trong một buổi dã ngoại của trường, bất ngờ TMB bị thầy giáo đố một câu như sau: "Một số có dạng ~p^{q}~ là lũy thừa cao của một số nguyên tố khi và chỉ khi ~p~ là một số nguyên tố và ~q > 1~. Thầy sẽ cho em một số ~N~ bất kỳ và em hãy cho biết đó có phải là lũy thừa cao của một số nguyên tố hay không? ". Không phải lúc nào cũng mang theo máy tính bên mình, đây là lúc TMB cần bạn.

Yêu cầu: Cho số ~N~, hãy giúp TMB trả lời câu đố của thầy giáo, nếu ~N~ là lũy thừa cao của một số nguyên tố thì in ra ~2~ số ~p~ và ~q~ tương ứng, nếu không thì ghi ~0~.

Input

  • ~1~ dòng duy nhất chứa ~n~

Output

  • ~1~ dòng duy nhất là kết quả

Giới hạn

~n \le 10^{18}~

Sample Input 1

27

Sample Output 1

3 3

Sample Input 2

10

Sample Output 2

0

Comments

Please read the guidelines before commenting.



  • 29
    YugiHackerKhongCopCode   commented on Dec. 16, 2021, 6:05 p.m.

    Spoil thuật không miller rabin

    Chia thành 2 trường hợp

    q>=3

    p <= 10^6

    Duyệt qua các số từ 2 đến 10^6, nếu n%i == 0 và i^q == n thì in ra kết quả (điều kiện là số mũ phải > 1)

    q = 2

    x = sqrt(n). Nếu x * x == n thì x là số nguyên tố và là kết quả

    chứng minh x là số nguyên tố:

    n = x * x, n <= 10^18

    => x<=10^9

    n không chia hết cho các số từ 2 đến 10^6

    => x không chia hết cho các số từ 2 đến 10^6

    => x là số nguyên tố


  • 5
    SPyofgame   commented on Oct. 7, 2021, 10:06 p.m.

    Unofficial Solution

    https://hackmd.io/@Editorial-Slayers/c11prime - Click