从一个素数问题到优化算法的重要性

做题有感

方法一：直接计算判断

数学优化算法：遍历范围的缩小以减小耗时

遍历全部

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int isPrime1(int target) {
    int i;
    if (target <= 1){
        printf("error");
        return -1;
    }
    
    for (i = 2; i <= target; i++) {
        if (target % i == 0)
            return 0;
    }
    
    return 1;
}

遍历至sqrt(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int isPrime2(int target) {
    int i;
    if (target <= 1){
        printf("error");
        return -1;
    }
    
    for (i = 2; i <= (int)sqrt(target); i++) {
        if (target % i == 0)
            return 0;
    }
    
    return 1;
}

继续分析，其实质数还有一个特点，除了 2 和 3，它总是等于 6x-1 或者 6x+1，其中 x 是大于等于1的自然数。

上面的结论证明如下： （1）6x 能被 6 整除； （2）6x+2 能被 2 整除； （3）6x+3 能被 3 整除； （4）6x+4 能被 2 整除。 那么，就只有 6x+1 和 6x+5 (即等同于6x-1) 可能是质数了。

又因为合数有个性质，合数肯定有一个小于或等于根号的质因数，所以如果 n 能被 6 倍数两侧的数（才有可能是质数）整除，那么 n 是合数，否则 n 是素数。所以循环的步长可以设为 6，然后每次只判断 6 两侧的数能否整除 n 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int isPrime3(int target) {
    int i;
    if (target <= 1){
        printf("error");
        return -1;
    }
    if (target % 6 !== 1 && target % 6 !==5)
        return 0;
    for (i = 5; i <= (int)sqrt(target); i += 6) {
        if (target % i == 0 && target % (i + 2) == 0)
            return 0;
    }
    
    return 1;
}

方法二：查素数表

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

1
2
3
4
5
6
7
8
9
10
11
12
13
//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;
}

方法三：筛法（得素数表）

普通筛法——埃拉托斯特尼（Eratosthenes）筛法

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void Eratprime(
    int* isprime,//判断素数的数组
    int upper_board//范围上限N
) 
{

    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;
        }
    }

}

线性筛法——欧拉筛法

思路: 我们再思考一下上面的埃拉托斯特尼筛法，会发现，在“剔除“非素数时，有些合数会重复赋值。这样就会增加复杂度，降低效率。

-> 用一个标识符避免重复筛选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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;
            }
        }
    }
}

参考：https://github.com/hairrrrr/C-CrashCourse/blob/master/content/c-notes/你不知道的几种素数判断方法，由浅入深，详解.md)