写一个判断素数的函数C++

以下是一个判断素数的函数实现示例，使用了试除法：

bool isPrime(int n) {
    if (n <= 1) return false; // 1不是素数
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false; // n能被i整除，则n不是素数
    }
    return true; // 判断完所有可能的因子，n是素数
}

该函数接受一个整数参数 `n`，返回一个布尔值，表示 `n` 是否是素数。该函数首先判断 `n` 是否小于等于 1，如果是，则直接返回 `false`，因为 1 不是素数。

然后使用试除法，从 2 开始枚举可能的因子，如果发现 `n` 能被某个数整除，则说明 `n` 不是素数，直接返回 `false`。如果枚举完了所有可能的因子，都没有发现能够整除 `n` 的数，那么 `n` 就是素数，返回 `true`。

相关问题

用c++写一个判断素数的函数

好的，以下是用 C 语言实现的判断素数的函数：

#include <stdio.h>
#include <math.h>

int is_prime(int n) {
    int i;
    if (n < 2) {
        return 0;
    }
    for (i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

int main() {
    int n;
    printf("请输入一个整数：");
    scanf("%d", &n);
    if (is_prime(n)) {
        printf("%d 是素数\n", n);
    } else {
        printf("%d 不是素数\n", n);
    }
    return 0;
}

在这个函数中，我们首先判断 n 是否小于 2，若小于 2，则直接返回 0，因为小于 2 的整数都不是素数。然后，我们循环从 2 到 sqrt(n)（sqrt 函数是 math.h 头文件中的一个函数，用于求平方根），如果 n 能被 i 整除，则 n 不是素数，返回 0。如果循环结束后都没有返回 0，说明 n 是素数，返回 1。

在 main 函数中，我们输入一个整数 n，调用 is_prime 函数判断 n 是否是素数，输出结果。

用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 位整数来进行快速幂运算，以避免数据溢出。