c语言判断素数的方法

在C语言中，判断一个数是否为素数的方法如下：

试除法

基本思想：用2到根号n之间的所有整数去除n，如果都无法整除，则n为素数。

代码示例：

c include <stdio.h> include <math.h> int is_prime（int n） { if （n <= 1） return 0； for （int i = 2； i <= sqrt（n）； i++） { if （n % i == 0） return 0； } return 1； } int main（） { int number； printf（"请输入一个整数： "）； scanf（"%d", &number）； if （is_prime（number）） { printf（"%d 是素数。\n", number）； } else { printf（"%d 不是素数。\n", number）； } return 0； }

质数筛

基本原理：初始化一个布尔型数组is_prime，长度为要检查的数的个数，初始值为true。从2开始，对每个数字i，如果is_prime[i]为true，则i是素数。对于i的所有倍数j（从i*i到n），将is_prime[j]设置为false。

代码示例：

c include <stdio.h> include <stdbool.h> include <math.h> include <string.h> void sieve_of_eratosthenes（int n） { bool is_prime[n + 1]； memset（is_prime, true, sizeof（is_prime））； is_prime = is_prime = false； for （int i = 2； i * i <= n； i++） { if （is_prime[i]） { for （int j = i * i； j <= n； j += i） { is_prime[j] = false； } } } for （int i = 2； i <= n； i++） { if （is_prime[i]） { printf（"%d ", i）； } } } int main（） { int n； printf（"输入一个正整数： "）； scanf（"%d", &n）； sieve_of_eratosthenes（n）； return 0； }

费马小定理

基本原理：对于任何素数p和任何整数a，a^p - a模p为0。我们可以使用此定理来判断一个数字是否为素数。

代码示例：

c include <stdio.h> include <math.h> include <stdbool.h> bool is_prime_fermat（int n, int a） { return pow（a, n - 1） % n == 1； } int main（） { int n； int a； printf（"输入一个正整数： "）； scanf（"%d", &n）； printf（"输入一个整数a （1 < a < n）: "）； scanf（"%d", &a）； if （is_prime_fermat（n, a）） { printf（"%d 可能是素数。\n", n）； } else { printf（"%d 不是素数。\n", n）； } return 0； }

这些方法中，试除法是最常用且高效的，适用于大多数情况。质数筛适用于需要生成素数列表的情况，而费马小定理适用于需要较高准确性的情况，但需要多次测试以提高可靠性。