在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`函数进行判断,最后输出结果。