用c++和AKS 算法写一个判断素数的函数

好的，以下是用 C++ 实现 AKS 算法判断素数的函数：

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

ll power(ll a, ll b, ll mod) {
    ll res = 1;
    while (b) {
        if (b & 1) res = (__int128) res * a % mod;
        a = (__int128) a * a % mod;
        b >>= 1;
    }
    return res;
}

bool is_prime(ll n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;

    ll r = sqrt(n);
    for (ll i = 5; i <= r; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }

    if (n <= r * r) return true;

    ll d = n - 1;
    while (d % 2 == 0) d /= 2;

    vector<ll> a = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for (ll i = 0; i < a.size(); i++) {
        if (a[i] >= n) break;

        ll x = power(a[i], d, n);
        if (x == 1 || x == n - 1) continue;

        bool flag = false;
        while (d != n - 1) {
            x = (__int128) x * x % n;
            d *= 2;
            if (x == 1) return false;
            if (x == n - 1) {
                flag = true;
                break;
            }
        }
        if (!flag) return false;
    }
    return true;
}

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

    ll r = 2;
    while (r * r <= n) {
        if (n % r == 0) {
            if (gcd(r, n / r) != 1) return false;
            else return true;
        }
        r++;
    }

    ll m = ((ll)log2(n) << 1) + 1;
    for (ll r = 2; r <= m; r++) {
        if (power(r, n, n) != r) return false;
    }

    return true;
}

int main() {
    ll n;
    cin >> n;
    if (is_prime(n)) {
        cout << "AKS says: " << is_prime_ak(n) << endl;
        cout << "It is a prime number!" << endl;
    } else {
        cout << "AKS says: " << is_prime_ak(n) << endl;
        cout << "It is not a prime number!" << endl;
    }
    return 0;
}

其中，`is_prime` 函数采用了 Miller-Rabin 算法进行素数判断，而 `is_prime_ak` 函数则是 AKS 算法的实现。

需要注意的是，在 AKS 算法中，判断 $a$ 和 $n$ 是否互质时，可以使用欧几里得算法来求最大公因数，因为 AKS 算法的时间复杂度已经足够低，不需要使用更快的算法。此外，在 AKS 算法中，我们需要使用 128 位整数来进行快速幂运算，以避免数据溢出。