---
tags: VNOJ, Prime, Brute-forces, Implementation, Math, Miller-Rabin, SPyofgame
title: 🌱 Số nguyên tố
author: Editorial-Slayers Team
license: Public domain
---

<style>
.markdown-body { max-width: 2048px; }
</style>

$\Huge \text{🌱 Số nguyên tố}$

-----

###### 🔗 Link: [Link](URL)
###### 📌 Tags: `Prime`, `Brute-forces`, `Implementation`, `Math`, `Miller-Rabin`
###### 👤 Writer: @SPyofgame
###### 👥 Contributor: [@Editorial Slayers Team](https://hackmd.io/@Editorial-Slayers)
###### 📋 Content:

[TOC]

-----
## Hướng dẫn

Nhận thấy $n = p^q$ mà $p$ nguyên tố nên $n \geq 2$

Lại có $n \leq 10^{18}$, và số nguyên tố nhỏ nhất là $p = 2$ nên $q \leq log_2(10^{18}) < 60$

Vậy ta duyệt qua $q = 2 \dots 60$, lấy $p = log_q(n)$ và kiểm tra xem $p$ có nguyên tố hay không là được

**Lưu ý:**

- Để tính $p = log_q(n)$ ta có thể dùng $p = n^{1/q}$, nếu bạn sợ sai số do số thực có thể duyệt thêm vài số lân cận
- Hoặc ta cũng có thể sài chặt nhị phân tìm $q$, nhưng hãy cận thận tràn số, nếu tràn số thì gán bằng $+\infty$
- $p$ nguyên tố khi $p$ không có ước trong đoạn $[2, \sqrt{p}]$ nên chỉ cần thử $O(\sqrt{p})$ lần
- Ngoài ra ta cũng có thể kiểm thử tính nguyên tố của $p$ bằng các thuật toán như Miller-Rabin

-----
### Code

> For constant $V = max(q) = 60$
> **Time:** $O(V \log_2 V \times \sqrt{n})$
> **Space:** $O(1)$
> **Algo:** Prime, Brute-forces, Implementation, Math
> [color=lightgreen]

:::success
:::spoiler Code

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

typedef long long ll;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;

bool isPrime(ll n)
{
    if (n < 2 || n == 4) return false;
    if (n == 2 || n == 3 || n == 5) return true;
    if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0) return false;

    for (int x = 5; 1LL * x * x <= n; x += 6)
        if (n % x == 0 || n % (x + 2) == 0)
            return false;
            
    return true;
}

ll pw(ll x, ll n)
{
    ll res = 1;
    for (; n > 0; n >>= 1)
    {
        if (n & 1)
        {
            if (res <= LINF / x)
                res *= x;
            else 
                res = +LINF;
        }

        if (x <= LINF / x)
            x *= x;
        else 
            x = +LINF;
    }

    return res;
}

int main()
{
    ll n;
    cin >> n;

    for (int q = 2; q <= 60; ++q)
    {
        ll p = pow(n, double(1.0) / q);
        while (pw(p, q) < n) ++p;
        while (pw(p, q) > n) --p;
        if (pw(p, q) == n)
        {
            if (isPrime(p))
            {
                cout << p << " " << q;
                return 0;
            }
        }
    }

    cout << 0;
    return 0;
}

:::

-----
### Code

> For constant $X$ (to boost miller-rabin test)
> For constant $V = max(q) = 60$
> **Time:** $O(V \log_2 V \times \log^5(n))$
> **Space:** $O(X)$
> **Algo:** Prime, Miller-Rabin, Implementation, Math
> [color=lightgreen]

:::success
:::spoiler Code

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

typedef long long ll;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const int X = 10101;

vector<int> prime, lpf;
void sieve(int n = X)
{
    prime.assign(1, 2);
    lpf.assign(n + 1, 2);
 
    for (int x = 3; x <= n; x += 2)
    {
        if (lpf[x] == 2) prime.push_back(lpf[x] = x);
        for (int i = 0; i < prime.size() && prime[i] <= lpf[x] && prime[i] * x <= n; ++i)
            lpf[prime[i] * x] = prime[i];
    }
}
 
const int MOD = 1e9 + 7;
ll fixMOD(ll x, const ll m = MOD)
{
    x %= m;
    if (x < 0) x += m;
    return x;
}
 
ll addMOD(ll a, ll b, const ll m = MOD)
{
    return fixMOD(a += b, m);
}
 
ll mulMOD(ll a, ll b, const ll m = MOD)
{
    if (!(a %= m)) return 0;
    if (!(b %= m)) return 0;
    if (abs(a) <= (1e18 + 118) / abs(b)) return fixMOD(a *= b, m);
 
    ll res = 0;
    if (abs(a) < abs(b)) swap(a, b);
    for (; b > 0; a <<= 1, b >>= 1)
    {
        if (a >= m) a -= m;
        if (b & 1) 
        {
            res += a;
            if (res >= m) res -= m;
        }
    }
 
    return res;
}
 
ll powMOD(ll x, ll n, const ll m = MOD)
{
    ll res = 1;
    for (; n > 0; n >>= 1)
    {
        if (n & 1) res = mulMOD(res, x, m);
        x = mulMOD(x, x, m);
    }
 
    return res;
}
 
bool mr_test(ll n, int a, ll d, int s)
{
    ll x = powMOD(a, d, n);
    if (x == 1 || x == n - 1) return false;
 
    for (int r = 1; r < s; ++r)
    {
        x = mulMOD(x, x, n);
        if (x == n - 1) return false;
    }
 
    return true;
}
 
bool miller_rabin(ll n, int k = 5)
{
    if (n < 4) return n == 2 || n == 3;
    for (int x : prime)
    {
        if (n == x) return true;
        if (n % x == 0) return false;
        if (1LL * x * x > n) break;
    }
 
    int s = __builtin_ctz(n - 1);
    ll d = (n - 1) >> s;
    for (int it = 1; it <= 5; ++it)
    {
        int a = 2 + rand() % (n - 3);
        if (mr_test(n, a, d, s)) return false;
    }
 
    return true;
}
 
bool isPrime(ll n)
{
    if (n < 2) return false;    
    if (n < lpf.size()) return lpf[n] == n;
    return miller_rabin(n);
}

ll pw(ll x, ll n)
{
    ll res = 1;
    for (; n > 0; n >>= 1)
    {
        if (n & 1)
        {
            if (res <= LINF / x)
                res *= x;
            else 
                res = +LINF;
        }

        if (x <= LINF / x)
            x *= x;
        else 
            x = +LINF;
    }

    return res;
}

int main()
{
    ll n;
    cin >> n;
    
    sieve();
    for (int q = 2; q <= 60; ++q)
    {
        ll p = pow(n, double(1.0) / q);
        while (pw(p, q) < n) ++p;
        while (pw(p, q) > n) --p;
        if (pw(p, q) == n)
        {
            if (isPrime(p))
            {
                cout << p << " " << q;
                return 0;
            }
        }
    }

    cout << 0;
    return 0;
}

:::