使用Miller-Rabin素性检验算法判断输入的整数是否为素数用C语言来实现

Miller-Rabin算法是一种常用的素性检验算法，它可以在多项式时间内判断一个数是否为素数。下面是使用C语言实现Miller-Rabin算法的代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 定义快速幂函数
long long fast_pow(long long a, long long b, long long p) {
    long long ans = 1;
    while (b) {
        if (b & 1) {
            ans = (ans * a) % p;
        }
        a = (a * a) % p;
        b >>= 1;
    }
    return ans;
}

// 定义Miller-Rabin素性检验函数
int is_prime(long long n, int k) {
    if (n < 2) {
        return 0;
    }
    if (n == 2 || n == 3) {
        return 1;
    }
    if (n % 2 == 0) {
        return 0;
    }

    // 将n-1分解为2^r * d的形式
    long long d = n - 1;
    int r = 0;
    while (d % 2 == 0) {
        d /= 2;
        r++;
    }

    // 进行k次测试
    for (int i = 0; i < k; i++) {
        long long a = rand() % (n - 3) + 2;  // 随机选择a，2 <= a <= n-2
        long long x = fast_pow(a, d, n);
        if (x == 1 || x == n - 1) {
            continue;
        }
        for (int j = 0; j < r - 1; j++) {
            x = (x * x) % n;
            if (x == n - 1) {
                break;
            }
        }
        if (x != n - 1) {
            return 0;
        }
    }
    return 1;
}

int main() {
    srand(time(NULL));  // 初始化随机数种子
    long long n = 123456789;  // 待判断的整数
    int k = 10;  // 进行10次测试
    if (is_prime(n, k)) {
        printf("%lld is prime.\n", n);
    } else {
        printf("%lld is not prime.\n", n);
    }
    return 0;
}

该程序中，首先定义了一个快速幂函数fast_pow，用于计算a^b mod p。然后定义了一个is_prime函数，用于判断n是否为素数。该函数接受两个参数，n为待判断的整数，k为进行测试的次数。

is_prime函数首先判断n是否小于2，是否等于2或3，是否为偶数，如果是则直接返回0或1。然后将n-1分解为2^r * d的形式，并进行k次测试。每次测试随机选择一个2 <= a <= n-2的整数，计算a^d mod n的值x，如果x等于1或n-1，则继续进行下一次测试；否则，进行r-1次平方运算，并检查是否等于n-1。如果不等于n-1，则n为合数，返回0；否则，继续进行下一次测试。如果进行了k次测试都没有得到结果，则n很可能是素数，返回1。

在main函数中，首先初始化随机数种子，然后定义了一个待判断的整数n和进行测试的次数k。最后调用is_prime函数进行判断，并输出结果。

注意，由于Miller-Rabin算法是概率性算法，因此在实际应用中需要进行多次测试，以提高正确性的概率。通常进行10次测试即可满足要求。