用c语言写7-3 【c0340】应用循环结构验证欧拉素数公式 分数 10 作者 c循环结构程

以下是用C语言编写的验证欧拉素数公式的程序：

#include <stdio.h>

// 欧拉素数公式：a^(p-1) ≡ 1 (mod p)，其中a和p为互质的正整数，p为素数
int is_prime(int num) {
    int a = 2;
    for (a = 2; a < num; a++) {
        if (num % a == 0) {
            return 0; // 不是素数
        }
    }
    return 1; // 是素数
}

int main() {
    int p;
    printf("请输入一个素数p：");
    scanf("%d", &p);

    int a;
    for (a = 1; a < p; a++) {
        int result = 1;
        int i;
        for (i = 1; i < p - 1; i++) {
            result = (result * a) % p;
        }
        if (result != 1) {
            printf("%d不是素数\n", p);
            return 0;
        }
    }

    printf("%d是素数\n", p);
    return 0;
}

程序的运行过程如下：

1. 程序提示用户输入一个素数p；
2. 程序用循环结构遍历所有1到p-1之间的a，对于每个a，计算a^(p-1) mod p的值；
3. 如果存在某个a满足a^(p-1) mod p != 1，则判定p不是素数；
4. 如果所有的a都满足a^(p-1) mod p == 1，则判定p是素数。

需要注意的是，验证欧拉素数公式只能判定素数，而不能判定合数。因此，如果程序输出p是素数，则p可能是素数，但不一定是素数；如果程序输出p不是素数，则p一定是合数。