c语言编程题怎么看质数

时间:2025-03-04 22:01:47 明星趣事

在C语言中判断一个数是否为质数,可以采用以下几种方法:

穷举法

从2开始逐个判断n是否能被2到n-1之间的数整除,如果存在能整除的数,则n不是质数;如果不存在能整除的数,则n是质数。

埃氏筛法

先将2到n之间的所有数标记为质数,然后从2开始,将每个质数的倍数标记为合数,直到遍历完2到n的所有数,标记完后剩下的未标记的数即为质数。

费马检测法

对于给定的数n,随机选取一个小于n的整数a,计算a^(n-1) % n的结果,如果结果等于1,则n可能是质数;如果结果不等于1,则n一定不是质数。

米勒-拉宾素数测试法

对于给定的数n,将n-1写成2^k * m的形式,其中k和m都是整数且m是奇数,随机选取一个小于n的整数a,计算a^m % n的结果,如果结果等于1或者等于n-1,则n可能是质数;如果结果不等于1且不等于n-1,则n一定不是质数。重复进行几次测试以增加正确性。

巧用平方根

检查从2到sqrt(n)(包括)之间是否有任何数能整除n。如果在这个范围内没有找到任何可以整除n的数,则n是质数。

```c

include

include

bool isPrime(int n) {

if (n <= 1) return false;

if (n == 2) return true;

if (n % 2 == 0) return false;

for (int i = 3; i * i <= n; i += 2) {

if (n % i == 0) return false;

}

return true;

}

int main() {

int num;

printf("请输入一个正整数: ");

scanf("%d", &num);

if (isPrime(num)) {

printf("%d 是质数\n", num);

} else {

printf("%d 不是质数\n", num);

}

return 0;

}

```

这个代码首先定义了一个`isPrime`函数,用于判断一个数是否为质数。然后在`main`函数中,读取用户输入的整数,并调用`isPrime`函数进行判断,最后输出结果。