素数的求法

Posted on | Edited on | In ,
| 3.5k | 30 mins.

定义

介绍如何求素数之前，首先得明白素数是什么？所谓素数（也叫质数），是指大于1，且只能被1和其本身整除的数（此定义与合数的定义相对）。

简便求法

在对时间复杂度没有要求的情况下，直接从定义出发，利用循环，一直做取余运算，就可以很容易的得到判断一个数字是否为素数的算法，具体如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool Is_Prime(int number) {
    bool flag = true;
    int i;
    if(number <= 1) {
        flag = false;
    } else {
        for(i = 2; i < number; i++) {
            if(number % i == 0) {
                flag = false;
                break;
            }
        }
    }
    return flag;
}

很明显，因为借助了一层循环，所以时间复杂度$O(n)$，优点就是十分容易理解了。

结合数学知识的优化

在理解了简便求法之后，来稍微思考一下，偶数能被2整除，所以肯定不是素数，如果一开始先判断number是不是偶数，然后在从 3 开始判断number是否能被奇数整除，如此一来，整个循环次数就是$(n - 3) / 2 + 1$（奇数每次增加2，所以分母为2）了，当$n$较大的时候，这个值是趋近于$n / 2$的。接着来改写一下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool Is_Prime(int number) {
    bool flag = true;
    int i;
    if(number <= 1 || (number % 2 == 0 && number != 2)) {
        flag = false;
    } else {
        for(i = 3; i < number; i += 2) {
            if(number % i == 0) {
                flag = false;
                break;
            }
        }
    }
    return flag;
}

相比简便求法，将总体时间缩短了一半，时间复杂度是$O(n/2)$。

实际上，循环区间可以缩减为$[3, \sqrt{number})$（此处的数学证明就不多说了😁，可以简单想一下，一个数$n$，对于$x <= n$，如果$n$能整除$x$，则$n$也一定能整除$n/x$，这两个数中必定有一个大于等于$\sqrt{n}$），具体如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool Is_Prime(int number) {
    bool flag = true;
    int i;
    if(number <= 1 || (number % 2 == 0 && number != 2)) {
        flag = false;
    } else {
        for(i = 3; i * i < number; i += 2) {
            if(number % i == 0) {
                flag = false;
                break;
            }
        }
    }
    return flag;
}

上述代码块中用i * i来代表平方根的写法较为常见，这样此算法的时间复杂度就为$O(\sqrt{n})$。
但是，i * i这种写法，会溢出，最好就使用sqrt函数。

转换思路

按照之前的做法，无论i的值是素数还是合数，都对number进行了整除的运算。实际上，判断number是否为素数，只需要在i的值为素数的情况下，判断number是否能被i整除即可，若能整除则不是素数，反之则是。
在进行上述计算的过程中，需要提前准备一张素数表来帮助计算，具体如下：

1
2
3
4
5
6
7
8
9
10
11
bool Is_Prime(int number, int Prime[], int NumOfPrime) {
    bool flag = true;
    int i;
    for(i = 0; i < NumOfPrime; i++) {
        if(a % Prime[i] == 0) {
            flag = false;
            break;
        }
    }
    return flag;
}

在计算的数据较大的情况下，无法直接给定素数表，需要边判断边更新，这样会消耗掉一定的时间，所以上述算法的实际时间复杂度$O(n) ∈ (\sqrt{n}, n/2)$，但此法很适合需要构造素数表并求和的场景。

紧接着刚才的思路，以2为例，在判断出其为素数后，其倍数$4、6、8、10...$就是非素数了，那么一次性将这些数字标记为非素数，也可以提高效率，这就是“筛选法”构造素数表，具体如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool IsPrime[NumOfPrime];
for(i = 2; i < NumOfPrime; i++) {
    IsPrime[NumOfPrime] = 1;
}
void Get_Prime() {
    int x, i;
    for(x = 2; x < MaxNum; x++) {
        if( IsPrime[x] ) {
            for(i = 2; i * x < MaxNum; i++) {
                IsPrime[i*x] = 0;
            }
        }
    }
}

粗略分析代码，可知此算法时间的复杂度为$O(n * loglog{n})$，之所以是这个时间复杂度，是因为一次性计算出了$[0, MaxNum)$这个区间内的所有素数，此算法实际效果较好，对于需要构造素数表的情况很方便。

扩展

上面介绍的“筛选法”，其实是古希腊数学家埃拉托色尼（Eratosthenes，274 B.C ~ 194 B.C）提出的一种筛选法，也称埃氏筛法。
实际上，结合利用素数表来判断素数的思路，对于合数而言，如果其只要被其最小质因子整除，即可判断其不是素数。那么去掉这部分重复计算的过程，不就可以提高效率了吗？
以16为例，在埃氏筛法中，$x = 2$时，筛选掉了$4、6、8、10...$，当$x = 3$时，又重复计算了$6、12...$等数。接着来修改下代码：

1
2
3
4
5
6
7
8
9
10
11
12
bool Number[MaxNum];
memset(Number, true, sizeof(Number));
int Prime[MaxNum], count = 0;
for(i = 2; i < MaxNum; i++) {
    if( Number[i] ) {
        Prime[count++] = i;
        for(j = 1; j <= num && i * Prime[j] <= n; j++) {
            Number[i * Prime[j]] = false;
            if(i % Prime[j] == 0) break;
        }
    }
}

上述代码的时间复杂度为$O(n)$（计算过程暂不深究），所以此种筛法也叫线性筛法，不过提升效率的代价就是多余的空间开销了，一般而言的优化都是用空间换时间这样的思路。

Buy me a coffee ? :)
0%