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++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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.


  • -1
    danglebinhnguyen2014  commented on Dec. 25, 2024, 5:07 a.m.

    spidi spidu


  • -5
    caoductai2012hk  commented on Dec. 23, 2024, 3:50 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -12
    ChiPhatNguyen  commented on June 23, 2024, 2:18 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -10
    hieuhfgr  commented on March 13, 2024, 6:28 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 86
    YugiHackerKhongCopCode  commented on Dec. 16, 2021, 11:05 a.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ố


  • 20
    SPyofgame  commented on Oct. 7, 2021, 3:06 p.m.

    Unofficial Solution

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