首页C语言判断是否为素数用sqrt

C语言判断是否为素数用sqrt

时间: 2025-01-30 18:06:25 浏览: 30

在C语言中，判断一个数是否为素数通常会利用其特性：除了1和它本身外，没有其他正因数。一个常见的优化方法就是不超过该数平方根的范围来检查因子。这是因为如果n不是素数，那么必定存在一个因子a使得1 < a ≤ √n，同时存在另一个因子b使得b = n / a，其中a * b = n。所以，我们只需要验证从2到√n范围内的整数是否能整除n即可。下面是一个简单的示例函数，用于检查输入的数n是否为素数： ```c #include <stdio.h> #include <math.h> int is_prime(int n) { if (n <= 1) { return 0; // 小于等于1的数不是素数 } else if (n == 2 || n == 3) { return 1; // 2和3是素数 } else if (n % 2 == 0) { // 偶数直接排除，除了2 return 0; } else { int sqrt_n = sqrt(n); // 取n的平方根作为上限 for (int i = 3; i <= sqrt_n; i += 2) { // 检查奇数因子 if (n % i == 0) { return 0; // 如果找到因子，说明不是素数 } } return 1; // 未找到因子，是素数 } } int main() { int num; printf("请输入一个数字："); scanf("%d", &num); if (is_prime(num)) { printf("%d是素数\n", num); } else { printf("%d不是素数\n", num); } return 0; }

阅读全文