c语言判断是否为素数的函数(c语言编写判断素数的函数)

什么是素数？

素数指的是只能被1和自己整除的正整数。比如2、3、5、7都是素数，而4、6、8不是素数。判断一个数是否为素数可以通过试除法、欧拉筛等方法。

如何用C语言判断素数？

一个最简单直接的方法就是从2开始，一直除到这个数字的平方根。如果在整除过程中发现一个因子，就可以判定这个数不是素数。

int is_prime(int n) {
    if (n == 1) return 0;  //特判1,不是素数
    int q = (int)sqrt(n);  //取整数部分，即平方根
    for (int i = 2; i <= q; i++) {
        if (n % i == 0) return 0;  //如果能整除，不是素数
    }
    return 1;  //否则是素数
}

这个函数首先排除1，因为1不是素数。对于大于1的数，计算出它的平方根q。然后从2到q遍历，每次判断能否整除n。如果找到一个因子，函数就直接返回0，表示n不是素数。如果一直到q都没有找到因子，就证明n是素数，函数返回1。

如何优化C语言的素数判断？

上述的方法已经足够简单有效，但是当判断的数比较大时，循环次数太多，效率较低。实际上还有一些很好的优化方式可以提高代码的效率。

一个比较简单的优化方式是只遍历奇数。为什么？因为偶数（除2以外）都不可能是素数，所以我们只需要判断奇数。这样一来，循环次数就减少了一半。

int is_prime(int n) {
    if (n == 1) return 0;  //特判1,不是素数
    if (n == 2) return 1;  //特判2,是素数
    if (n % 2 == 0) return 0;  //既不是1也不是2并且是偶数，不是素数
    int q = (int)sqrt(n);  //取整数部分，即平方根
    for (int i = 3; i <= q; i += 2) { //只遍历奇数
        if (n % i == 0) return 0;
    }
    return 1;
}

另一个优化方式是用质数表。我们知道，质数表就是一个存储素数的数组，在判断某个数是否为素数时，只需要遍历这个数之前的质数，并判断是否能整除即可。

#define MAXN 100000  //宏定义，表示质数表最大容量
int prime[MAXN], flag[MAXN];  //分别表示质数表和标记数组
int cnt = 0; //计数器，表示质数表中的质数个数

void find_primes(int n) { //求出质数表，参数n表示最大的数
    memset(flag, 0, sizeof(flag)); //初始化标记数组为0，表示都未标记
    for (int i = 2; i <= n; i++) {
        if (flag[i]) continue; //如果这个数已经被标记为非素数，就直接跳过
        prime[cnt++] = i; //否则这个数是素数，加入质数表中
        for (int j = i*i; j <= n; j += i) {
            flag[j] = 1; //标记所有能整除i的数
        }
    }
}

int is_prime(int n) { //优化后的素数判断函数
    if (n == 1) return 0;  //特判1,不是素数
    if (n == 2) return 1;  //特判2,是素数
    if (n % 2 == 0) return 0;  //既不是1也不是2并且是偶数，不是素数
    int q = (int)sqrt(n);  //取整数部分，即平方根
    for (int i = 0; i < cnt && prime[i] <= q; i++) {
        if (n % prime[i] == 0) return 0; //判断是否能被质数表中的数整除
    }
    return 1;
}

这个算法不仅简单高效而且可以用在很多求解问题中，比如质数分解、筛法求素数等等。