素数

素数

一些定理性质

• 唯一分解定理

• 威尔逊定理：

  \(p\)是质数，则有\((p - 1) ! \equiv -1 \pmod p\)

  逆定理同时成立，如果有\((p - 1) ! \equiv -1 \pmod p\)，则\(p\)一定是质数。

  有\(((p - 1) ! + 1) \equiv 0 \pmod p\)可以通过\(\sin(\pi((n - 1)! + 1) / n) = 0\)来得到素数所在点函数。

• 费马小定理：

  假设\(p\)是一个质数，\(a\)不是\(p\)的倍数，则有\(a^{p - 1} \equiv 1\pmod p\)，证明如下

  我们分别取\(i * a \pmod p\)的值，\(for i in range(1, p)\)，由于\(i\)与\(p\)互质，\(a\)与\(p\)互质，所以，这些取模后的值是一个\((1 ~ n - 1)\)的排列，那么另这\(p - 1\)个数相乘，得到的就是\(a ^ {p - 1} * (p - 1)! \pmod p = (p - 1)!\)，因为\((p - 1) ! \pmod p != 0\)，所以两边同时约去得到\(a ^ {p - 1} \equiv 1 \pmod p\)。

Miller_Rabin素数测试

利用了\(a^{p} \equiv a \pmod p\)，这一性质来对素数进行判定，但是具体的证明我也没仔细看，就是测试一个数字之后就能有\(1/ 4\)的概率证明其不是质数，然后通过多测试几个数，就可以几乎精确的得到这个数是不是质数。

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;

const double eps = 1e-7;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;

inline ll read() {
    ll f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    } 
    while(c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return f * x;
}


ll qpow(ll a, ll n, ll mod) {
    ll ans = 1;
    while(n) {
        if(n & 1)   ans = (ans * a) % mod;
        n >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}

bool miller_rabin(ll a) {
    if(a == 2)  return true;
    for(int i = 1; i <= 10; i++) {
        ll temp = rand() % (a - 2) + 2;
        if(qpow(temp, a, a) != temp)    return false;
    }
    return true;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    srand(time(0));
    ll a;
    while(scanf("%lld", &a) != EOF) {
        if(miller_rabin(a)) puts("prime");
        else    puts("not");
    }
    return 0;
}

欧拉公式与欧拉定理

欧拉公式\(\phi(n) = x\)，\(x\)是小于\(n\)并且与\(n\)互质的数字的个数，有\(\phi(8) = 4 (1, 3, 5, 7)\)。

欧拉公式成立的几个定理：

• 如果\(p\)是质数，则有\(\phi(p) = p - 1\)，这是显然成立的。

• 如果\(p\)是质数，则\(\phi(p^i) = (p - 1) * p ^ {i - 1}\)，证明：

  在\([1, p ^ i)\)之间，与\(p\)互质的数有\(p* t(t = 1, 2, 3, …… p ^ {i - 1} - 1)\)，所以\(\phi(p^i) = p ^ i - 1 - (p ^ {i - 1} - 1) = (p - 1) * p ^ {i - 1}\)

• \(\phi(n) = n * (1 - 1 / p_1) * (1 - 1 / p_2) …… (1 - 1 / p_{n - 1}) * (1 - 1 / p_{n})\)，\(p_i\)是\(n\)的质因数，例如：\(8 = 2 ^ 3， \phi(8) = 8 * (1 - 1 / 2) = 4\)

• 如果\(a, b\)互质，则有\(\phi(a * b) = \phi(a) * \phi(b)\)，证明：

  可用上述的第三个定理来说明，\(a, b\)中的质因数是互质的，所以，任何两个\(p_{i}\)是互质的，然后显然成立。

欧拉定理

\(a, m\)互质有\(a ^ {\phi(m)} \equiv 1 \pmod m\)，当\(m\)时质数的时候，也就是\(a ^ {m-1} \equiv 1 \pmod m\)

欧拉筛(素数+欧拉函数)

最后给上素数筛和欧拉函数的线性求解法。

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;

const double eps = 1e-7;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;

inline ll read() {
    ll f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    } 
    while(c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return f * x;
}

const int N = 1e5 + 10;

int prime[N], phi[N], cnt = 0;
bool st[N];

void init() {
    phi[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!st[i]) {
            // cout << i << endl;
            prime[cnt++] = i;
            phi[i] = i - 1;
        }
        for(int j = 0; j < cnt && i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}


int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    return 0;
}