你不知道的几种素数判断方法，由浅入深，详解

我们要判断素数，首先要知道素数的定义。

素数：质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数;否则称为合数。

知道了素数的定义，那么我们应该想一下，如何去判断一个数是否为素数？

一种思路是，我们在每次得到一个数后，都去计算，去尝试因式分解它，看它除了1和自身之外还有没有其他因子
另一种是，我们去查阅素数表，看这个数在不在素数表上。那我们就要先得到素数表。

以下除了第一种方法，第2~4种方法都是用第二种思路做的
当要判断的目标数很少时，第一种高效。但是当给定的目标数组很多，数也很大时。后面的思路配上高效的查找算法，显然更高效

方法1：暴力求解

1-1:稍微动动脑

思想：
根据素数的定义思考。素数是大于1的自然数，除了1和自身外，其他数都不是它的因子。
那我们就可以用一个循环，从2开始遍历到这个数减去1，如果这个数都不能被整除，那么这个数就是素数。
也就是说：
给定一个数 n , i 从 2 开始取值，直到 n - 1(取整数),如果 n % i != 0 , n 就是素数
进一步思考，有必要遍历到 n - 1 吗？
除了1以外，任何合数最小的因子就是2，那最大的因子就是 n/2
那我们就遍历到 n/2就足够了

这样我们就可以写出这个算法的核心代码：

int isPrime(int target) {

    int i = 0;

    if (target <= 1) {
        printf("illegal input!\n");//素数定义
        return -1;
    }

    for (i = 2; i <= target / 2; i++) {
        if (target % i == 0)
            return 0;//不是素数直接返回0
    }

    return 1;//是素数返回1
}

点击并拖拽以移动

1-2：再进一步

思想：

在上面的基础上，其实不需要遍历到 n/2，只需要到根号n（包含根号n）就可以了。为什么呢？这是个数学问题，大家自行思考一下。

核心代码：

int isPrime(int target) {

    int i = 0;

    if (target <= 1) {
        printf("illegal input!\n");//素数定义
        return -1;
    }

    for (i = 2; i <= (int)sqrt(target); i++) {
        if (target % i == 0)
            return 0;
    }

    return 1;
}

点击并拖拽以移动

从第二种方法开始，我们都是先完成判断素数数组，然后用二分法去查找判断数组

这里说一下以下三种方法牵扯的概念：

范围：1 ~ 范围上限N

范围上限N：判断素数需要用户输入随机素数，这个随机素数的范围是1 ~ N

判断素数数组：将数组的下标与1 ~ N的自然数一一对应起来。
判断 1到N 的自然数是否为素数，其实就是判断数组的下标是否为素数，如果是给这个下标所对应的判断素数数组元素赋1，否则赋0
比如：我要判断3是否为素数，我们就找到判断素数数组isPrime中的下标为3的元素，即：isPrime[3]
如果 3 是素数，赋值1，即isPrime[3] = 1
如果 3 不是素数，赋值0 ，即isPrime[3] = 0
这样我们在用二分法查找时，查找数组下标就可以，找到下标后返回下标对应的判断素数数组的值。
如果是1说明下标对应的自然数是素数，否则不是

方法2：用素数表来判断素数

思路：
如果一个数不能整除比它小的任何素数，那么这个数就是素数
这种“打印”素数表的方法效率很低，不推荐使用，可以学习思想

核心代码：

//target：输入的要查找的数
//count：当前已知的素数个数
//PrimeArray：存放素数的数组
int isPrime(int target, int count, int* PrimeArray) {

    int i = 0;
    for (i = 0; i < count; i++) {
        if (target % PrimeArray[i] == 0)
            return 0;
    }

    return 1;
}

点击并拖拽以移动

方法3：普通筛法——埃拉托斯特尼(Eratosthenes)筛法

思路:
\1. 我们的想法是，创建一个比范围上限大1的数组，我们只关注下标为 1 ~ N（要求的上限）的数组元素与数组下标（一一对应）。
\2. 将数组初始化为1。然后用for循环，遍历范围为：【2 ~ sqrt(N)】。如果数组元素为1，则说明这个数组元素的下标所对应的数是素数。
\3. 随后我们将这个下标（除1以外）的整数倍所对应的数组元素全部置为0，也就是判断其为非素数。
这样，我们就知道了范围内（1 ~ 范围上限N）所有数是素数（下标对应的数组元素值为1）或不是素数（下标对应的数组元素值为0）

用百度百科对埃拉托斯特尼筛法简单描述：要得到自然数n以内的全部素数，必须把不大于的所有素数的倍数剔除，剩下的就是素数。

核心代码：

//                 判断素数的数组    范围上限N
void Eratprime(int* isprime, int upper_board) {

    int i = 0;
    int j = 0;
    //初始化isprime
    for (i = 2; i <= upper_board; i++)
        isprime[i] = 1;


    for (i = 2; i < (int)sqrt(upper_board); i++) {
        if (isprime[i]) {
            isprime[i] = 1;
        }
        for (j = 2; i * j <= upper_board; j++) {//素数的n倍（n >= 2）不是素数
            isprime[i * j] = 0;
        }
    }

}

点击并拖拽以移动

方法4：线性筛法——欧拉筛法

思路:
我们再思考一下上面的埃拉托斯特尼筛法，会发现，在“剔除“非素数时，有些合数会重复赋值。这样就会增加复杂度，降低效率。
比如：范围上限N = 16时
2是素数，剔除”2 的倍数“，它们是：4，6， 8，10， 12， 14， 16
3是素数，剔除”3 的倍数”，它们是，6，9，12，15
6，12是重复的。如何减少重复呢？

核心代码：

void PrimeList(int* Prime, bool* isPrime, int n) {

    int i = 0;
    int j = 0;
    int count = 0;

    if (isPrime != NULL) {//确保isPrime不是空指针
        //将isPrime数组初始化为 1
        for (i = 2; i <= N; i++) {
            isPrime[i] = true;
        }
    }

    if (isPrime != NULL && Prime != NULL) {
        //从2遍历到范围上限N
        for (i = 2; i <= N; i++) {
            if (isPrime[i])//如果下标（下标对应着1 ~ 范围上限N）对应的isPrime值没有被置为false，说明这个数是素数，将下标放入素数数组
                Prime[count++] = i;
            //循环控制表达式的意义：j小于等于素数数组的个数 或 素数数组中的每一个素数与 i 的积小于范围上限N
            for (j = 0; (j < count) && (Prime[j] * (long long)i) <= N; j++)//将i强制转换是因为vs上有warning，要求转换为宽类型防止算术溢出。数据上不产生影响
            {
                isPrime[i * Prime[j]] = false;//每一个素数的 i 倍（i >= 2）都不是素数，置为false

                //这个是欧拉筛法的核心，它可以减少非素数置false的重复率
                //意义是将每一个合数（非素数）拆成 2（最小因数）与最大因数 的乘积
                if (i % Prime[j] == 0)
                    break;
            }
        }
    }
}

点击并拖拽以移动

如果你没有理解，可以参考下例

点击并拖拽以移动

[以上四种算法的完整代码在我的github上，帮助到你了不妨给我点个star哦~](https://github.com/hairrrrr/win.ccode/tree/master/Pactise/2020WinterVacation/Prime/Prime Judgement)

感谢指出我错误的微信网友：大异小同。

本次修改内容：

\1. 1-1中的代码，for循环的循环控制 i < target / 2 改为 i <= target

错误情况：当 target == 4 时，target / 2 的值是 2，i 从 2开始，如果循环控制是：i < target / 2, 则不会进入 for 循环，所以会将 4 误判为素数

\2. sqrt 函数的返回值是 double 类型。

将 i <= sqrt(target) 改为 i <= (int)sqrt(target)

sqrt 函数的函数原型：double sqrt(double arg);

2020 - 2 - 24 日修改：