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

判断一个数是否是素数的C语言实现

素数（质数）是指大于1的自然数，除了1和它本身外不能被其他自然数整除的数,以下是几种在C语言中判断素数的方法：

简单试除法（适用于小数字）

#include <stdio.h>
#include <stdbool.h> // 使用bool类型需要包含此头文件
bool isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}
int main() {
    int number;
    printf("请输入一个整数: ");
    scanf("%d", &number);
    if (isPrime(number)) {
        printf("%d 是素数\n", number);
    } else {
        printf("%d 不是素数\n", number);
    }
    return 0;
}

优化试除法（排除偶数）

#include <stdio.h>
#include <stdbool.h>
bool isPrime(int num) {
    if (num <= 1) return false;
    if (num == 2) return true;      // 2是唯一的偶素数
    if (num % 2 == 0) return false; // 排除所有偶数
    // 只需检查奇数因子
    for (int i = 3; i * i <= num; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}
int main() {
    int number;
    printf("请输入一个整数: ");
    scanf("%d", &number);
    if (isPrime(number)) {
        printf("%d 是素数\n", number);
    } else {
        printf("%d 不是素数\n", number);
    }
    return 0;
}

更高效的判断（适用于大数字）

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
bool isPrime(int num) {
    if (num <= 1) return false;
    if (num <= 3) return true;      // 2和3是素数
    if (num % 2 == 0 || num % 3 == 0) return false;
    // 检查6k ± 1形式的因子
    for (int i = 5; i * i <= num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}
int main() {
    int number;
    printf("请输入一个整数: ");
    scanf("%d", &number);
    if (isPrime(number)) {
        printf("%d 是素数\n", number);
    } else {
        printf("%d 不是素数\n", number);
    }
    return 0;
}

说明

1. 基本思路：检查从2到√n的所有整数是否能整除n,如果能整除则不是素数。
2. 优化点：
   • 排除所有偶数（除了2）
   • 只检查6k ± 1形式的数（所有素数大于3都可以表示为6k±1）
   • 提前检查一些特殊情况（如2、3）
3. 时间复杂度：最坏情况下为O(√n)
4. 适用范围：对于非常大的数（如超过10^18），需要使用更高级的算法（如Miller-Rabin素性测试）

选择哪种方法取决于你的具体需求，对于大多数编程竞赛和日常应用,方法三已经足够高效。