算法1:素数问题的三种解决方法:一般法+两个筛子(例子:哥德巴赫猜想)
算法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=p∗M
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;
}
以上就是本次分享的全部内容啦,有问题可以在评论区提出,对大家有帮助的话希望可以不吝啬你们的点赞。
我也会继续更新我接下来的算法学习之旅,有兴趣的可以关注我。