owned this note
owned this note
Published
Linked with GitHub
---
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
```cpp=
#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
```cpp=
#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;
}
```
:::