C语言如何判断一个数是否为质数？

在C语言中,判断一个数是否为素数（质数）的基本思路是：检查该数是否能被1和它本身以外的任何整数整除，如果存在这样的整数，则它不是素数；否则，它是素数。

核心思路

1. 素数定义：大于1的自然数，除了1和它本身外，没有其他正因数。
2. 优化思路：
   • 不需要检查到 n-1，只需检查到 sqrt(n) 即可，因为如果 n 有一个大于 sqrt(n) 的因数，那么它必然对应一个小于 sqrt(n) 的因数。
   • 排除小于等于1的数（非素数）。
   • 2是唯一的偶素数,可以单独处理。

方法1：基础实现（从2到n-1检查）

#include <stdio.h>
#include <stdbool.h> // 使用bool类型
bool isPrime(int n) {
    if (n <= 1) {
        return false; // 小于等于1的数不是素数
    }
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return false; // 能被整除，不是素数
        }
    }
    return true; // 是素数
}
int main() {
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);
    if (isPrime(num)) {
        printf("%d is a prime number.\n", num);
    } else {
        printf("%d is not a prime number.\n", num);
    }
    return 0;
}

方法2：优化实现（检查到√n）

#include <stdio.h>
#include <stdbool.h>
#include <math.h> // 使用sqrt函数
bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}
int main() {
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);
    if (isPrime(num)) {
        printf("%d is a prime number.\n", num);
    } else {
        printf("%d is not a prime number.\n", num);
    }
    return 0;
}

方法3：进一步优化（跳过偶数）

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true; // 2是素数
    if (n % 2 == 0) return false; // 排除其他偶数
    for (int i = 3; i <= sqrt(n); i += 2) { // 只检查奇数
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}
int main() {
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);
    if (isPrime(num)) {
        printf("%d is a prime number.\n", num);
    } else {
        printf("%d is not a prime number.\n", num);
    }
    return 0;
}

关键点说明

1. 时间复杂度：
   • 方法1：O(n)
   • 方法2：O(√n)（显著优化）
   • 方法3：O(√n / 2)（进一步优化）
2. 边界情况：
   • 处理 n <= 1（非素数）。
   • 单独处理 n == 2（唯一的偶素数）。
3. 数学优化：
   • 只需检查到 sqrt(n)，因为因数成对出现。
   • 跳过偶数（除了2），减少不必要的计算。

测试示例

• 输入：7
  输出：7 is a prime number.
• 输入：10
  输出：10 is not a prime number.
• 输入：1
  输出：1 is not a prime number.

选择方法3是效率较高的实现,适合大多数场景。