欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法1:素数问题的三种解决方法:一般法+两个筛子(例子:哥德巴赫猜想)

程序员文章站 2024-03-15 17:33:12
...

算法1:素数问题的三种解决方法:一般法+两个筛子(例子:哥德巴赫猜想)

素数定义:质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。

1既不是素数也不是合数

1.一般法(一定优化的素数判定)

先把代码片贴上:

int is_prime (int n){
    if (n == 1) return 0; //1既不是合数也不是素数
    if (n == 2) return 1;//把2拿出讨论
    else{
        for (int i = 2; i < (int)(sqrt(n)+1); i++){
            if (n % i == 0) return 0;
        }
        return 1;
    }
}

在代码的第5行,进行了代码优化。
如果条件判定为 i < n,那么需要进行n - 3次循环。如果要输出一定范围内的素数的话,也就代表着其时间复杂度为O(n²)计算结果会非常耗时。
那么为什么可以写成sqrt(n) + 1呢?
是因为
n = n ∗ n n = \sqrt{n} * \sqrt{n} n=n n
即假如n有因数,一定会有一个大于等于根号n,一个小于等于根号n的因数。

比如8的因数2和4

因为根号n不都是整数,直接(int)的话会舍去解,故要加一。

这个优化还是比较显著的,比如n = 10000时,本需要循环10000次,而优化后只需要100次了

优化后的代码的时间复杂度大概是O( x 2 x ^ 2 x2)

那么能不能继续优化呢,那就要请出我们nb的东西——

2.素数筛

这次我们先讲方法,素数筛的核心只有一句话:

用素数标记合数

没错,就是如此简单的一句话,便可以将时间复杂度大大降低、

首先,我们定义一个数组,并将其所有元素初始化为0:

#define MAX_N 100
int prime[MAX_N + 5] = {0};

而后定义一个函数进行判定,在函数中我们进行循环,找出其中的素数进行向后标记,而合数则不做理会.

void is_prime1 (){
    for (int i = 2; i < MAX_N; i++){
        if (prime[i]) continue;
        . . .
    }
}

此时i = 2,prime[2] = 0;我们接下来要做的就是将以2为因数的合数都标记掉:

        for (int j = 2 * i; j <= MAX_N; j += i)
            prime[j] = 1;

如果再优化一下即向去标记合数,比如6这一合数,本来被2和3标记,而现在我3不去标记6,你2想从4开始标那就从4开始,顺便帮我把6标了,我3只标记9以上的数:

        for (int j = i * i; j <= MAX_N; j += i)
            prime[j] = 1;

又因为i²数值过大可能造成不必要的麻烦,所以我们不妨

        for (int j = i; j <=MAX_N / i; j++)
            prime[j * i] = 1;

我们还可以做的一个操作是,将prime[0]作为一个计数器,将质数按顺序储存到prime[]数组中

把整体代码贴上

#define MAX_N 100
int prime[MAX_N + 5] = {0};

void is_prime1 (int n){
    for (int i = 2; i < MAX_N; i++){
        if (prime[i]) continue;
        prime[++prime[0]] = i;//将质数存储进prime中
        for (int j = i; j <=MAX_N / i; j++)
            prime[j * i] = 1;
    }
}

至此,素数筛优化完毕,其时间复杂度接近O(n),是为O(n log log n)

但是即使很接近O(n),可其复杂度依旧不是O(n),那么有没有一种办法可以将其复杂度降到O(n)呢?

最后,请出我们的主角:

3.线性筛

依旧的先讲方法,线性筛的核心也只有一句话:

每一个合数都用其最小质因子来标记

如果说每一个合数N都用最小质因子p来标记的话,则有:
N = p ∗ M N = p * M N=pM
M 就是另一个因子,也即是合数N的最大因子。

那我们不妨将其反过来,用这个最大因子去找素数,二者的乘积就是一个合数,那样我们就可以标记了。

且每一个合数都是用最小质因子标记的,所以只标记了一次,那么其时间复杂度自然为O(n)了。

首先,我们需要将素数储存到一个prime[]素数表中

void nb_prime(){
    for (int i = 2; i <= MAX_N; i++){
        if(!prime[i]) prime[++prime[0]] = i;
        ...
    }

定义一个计数器j,将素数表中的素数一个一个取出,标记它能标记的最大的合数。

		for (int j = 1; j <= prime[0]; j++){
            if (i * prime[j] > MAX_N) break;
            prime[prime[j] * i] = 1;
            if (i % prime[j] == 0) break;
        }

为什么判定条件是i % prime[j] == 0呢?

因为当i是质数时,只有遍历到自己,才会停止标记,这没什么问题。

比如i = 3会标记6,9。

当i是合数时,如果遍历到的质数是它的因子,那么就一定是最小质因子,那么i就可以写成p乘以M的形式。那它去遍历下一个质数并且表示时,被标记的数的最小质因子就是p了。

比如i = 8时,8 % 2 =0 如果没有退出,去继续遍历3的话

8 * 3 = 2 * 4 * 3 = 2 * 12

如此,这个算法就算是写完了。

整体代码如下

#define MAX_N 100
int prime[MAX_N + 5] = {0};

void nb_prime(){
    for (int i = 2; i <= MAX_N; i++){
        if(!prime[i]) prime[++prime[0]] = i;
        for (int j = 1; j <= prime[0]; j++){
            if (i * prime[j] > MAX_N) break;
            prime[prime[j] * i] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

一个小例子

题目:哥德巴赫猜想中写到,一个充分大的偶数(大于等于4),它可以分解为两个素数(质数)的和。

任务是将输入的偶数n ,分解为两个素数的所有可能打印出来。

例如:

8 = 3 + 5.

2008 = 5 + 2003

代码实现

#include<stdio.h>
#define MAX_N 8000000
int prime[MAX_N + 5];
int is_prime[MAX_N + 5];
void nb_prime(){
    for (int i = 2; i <= MAX_N; i++){
        if(!prime[i]) prime[++prime[0]] = i;
        for (int j = 1; j <= prime[0]; j++){
            if (i * prime[j] > MAX_N) break;
            is_prime[prime[j] * i] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

int main(){
    nb_prime();
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= prime[0] && prime[i] <= n/2; i++){
        if (!is_prime[n - prime[i]]){
            printf("%d = %d + %d\n", n, prime[i], n - prime[i]);
            break;
        }
    }
    return 0;
}

以上就是本次分享的全部内容啦,有问题可以在评论区提出,对大家有帮助的话希望可以不吝啬你们的点赞。

我也会继续更新我接下来的算法学习之旅,有兴趣的可以关注我。