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

📌 Tags: Prime, Brute-forces, Implementation, Math, Miller-Rabin
👤 Writer: @SPyofgame
👥 Contributor: @Editorial Slayers Team
📋 Content:

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

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

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;
}
Select a repo