C语言中怎么判断质数

什么是质数

质数，也叫素数，是一种特殊的整数，它只能被1和自身整除，不能被其他数整除。

方法一：暴力枚举

对于一个数n，可以从2到n-1枚举每一个数i，看是否能被n整除。如果找到一个i可以被n整除，说明n不是质数。否则，说明n是质数。

int is_prime(int n) {
    if(n <= 1) return 0;  //1不是质数
    //枚举2到n-1
    for(int i = 2; i < n; i++) {
        if(n % i == 0) {
            return 0;  //能被整除，不是质数
        }
    }
    return 1;  //不能被整除，是质数
}

方法二：优化枚举

在方法一的基础上，可以进行一些优化。首先，只需要枚举到n的平方根。因为不可能存在两个大于平方根的数相乘等于n。此外，可以先判断n是否能被2整除，这样在后续枚举中，可以每次加2，跳过偶数，进一步减少时间复杂度。

int is_prime(int n) {
    if(n <= 1) return 0;
    if(n == 2) return 1;  //2是质数
    if(n % 2 == 0) return 0;  //偶数不是质数
    //枚举2到sqrt(n)
    int sqr = (int)sqrt(1.0 * n);
    for(int i = 3; i <= sqr; i += 2) {
        if(n % i == 0) {
            return 0;
        }
    }
    return 1;
}

方法三：埃氏筛法

埃氏筛法是一种常见的筛法，可以筛选出某个范围内的所有质数。具体方法是：从2开始，将每个质数的倍数都标记为合数，直到无法继续标记为止。标记完成后，剩余未被标记的数即为质数。

void prime_sieve(int n) {
    int prime[n+1];
    memset(prime, 1, sizeof(prime));  //初始化都是质数
    prime[0] = prime[1] = 0;  //0和1不是质数
    int sqr = (int)sqrt(1.0 * n);
    for(int i = 2; i <= sqr; i++) {
        if(prime[i]) {  //i是质数
            for(int j = 2 * i; j <= n; j += i) {  //i的倍数都不是质数
                prime[j] = 0;
            }
        }
    }
    //输出质数
    for(int i = 2; i <= n; i++) {
        if(prime[i]) {
            printf("%d ", i);
        }
    }
}

总结

判断质数的方法有多种，其中暴力枚举是最简单的方法，但时间复杂度较高，埃氏筛法时间复杂度最低，可以筛选出某个范围内的所有质数，而优化枚举适用于判断单个数是否为质数。

返回的HTML内容： ```html

什么是质数

质数，也叫素数，是一种特殊的整数，它只能被1和自身整除，不能被其他数整除。

方法一：暴力枚举

对于一个数n，可以从2到n-1枚举每一个数i，看是否能被n整除。如果找到一个i可以被n整除，说明n不是质数。否则，说明n是质数。

int is_prime(int n) {
    if(n <= 1) return 0;  //1不是质数
    //枚举2到n-1
    for(int i = 2; i < n; i++) {
        if(n % i == 0) {
            return 0;  //能被整除，不是质数
        }
    }
    return 1;  //不能被整除，是质数
}

方法二：优化枚举

在方法一的基础上，可以进行一些优化。首先，只需要枚举到n的平方根。因为不可能存在两个大于平方根的数相乘等于n。此外，可以先判断n是否能被2整除，这样在后续枚举中，可以每次加2，跳过偶数，进一步减少时间复杂度。

int is_prime(int n) {
    if(n <= 1) return 0;
    if(n == 2) return 1;  //2是质数
    if(n % 2 == 0) return 0;  //偶数不是质数
    //枚举2到sqrt(n)
    int sqr = (int)sqrt(1.0 * n);
    for(int i = 3; i <= sqr; i += 2) {
        if(n % i == 0) {
            return 0;
        }
    }
    return 1;
}

方法三：埃氏筛法

埃氏筛法是一种常见的筛法，可以筛选出某个范围内的所有质数。具体方法是：从2开始，将每个质数的倍数都标记为合数，直到无法继续标记为止。标记完成后，剩余未被标记的数即为质数。

void prime_sieve(int n) {
    int prime[n+1];
    memset(prime, 1, sizeof(prime));  //初始化都是质数
    prime[0] = prime[1] = 0;  //0和1不是质数
    int sqr = (int)sqrt(1.0 * n);
    for(int i = 2; i <= sqr; i++) {
        if(prime[i]) {  //i是质数
            for(int j = 2 * i; j <= n; j += i) {  //i的倍数都不是质数
                prime[j] = 0;
            }
        }
    }
    //输出质数
    for(int i = 2; i <= n; i++) {
        if(prime[i]) {
            printf("%d ", i);
        }
    }
}

总结

判断质数的方法有多种，其中暴力枚举是最简单的方法，但时间复杂度较高，埃氏筛法时间复杂度最低，可以筛选出某个范围内的所有质数，而优化枚举适用于判断单个数是否为质数。

```