• • 题目描述
  • 线性筛
    • 分析
    • 代码
    • 时间复杂度
  • 参考文章

题目传送门

题目描述

哥德巴赫猜想的内容如下：

任意一个大于 4 的偶数都可以拆成两个奇素数之和。

例如：

8=3+5
20=3+17=7+13
42=5+37=11+31=13+29=19+23
现在，你的任务是验证所有小于一百万的偶数能否满足哥德巴赫猜想。

输入格式
输入包含多组数据。

每组数据占一行，包含一个偶数 n。

读入以 0 结束。

输出格式
对于每组数据，输出形如 n = a + b，其中 a,b 是奇素数。

若有多组满足条件的 a,b，输出 b?a 最大的一组。

若无解，输出 Goldbach’s conjecture is wrong.。

数据范围
6≤n<106
输入样例：
8
20
42
0
输出样例：
8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

线性筛

分析

注意线性筛过程中用到的st[]， st[i] = flase 表示i是质数

一开始我专门开了一个unordered_map来保存哪个数是质数，浪费了空间时间（多了一倍）

代码

#include
#include
#include
using namespace std;

const int N = 1000010;
int cnt = 0;
int primes[N];
int st[N]; //st[i]==true代表i这个数是其他数的倍数--即i不是质数
//unordered_map h;
int n;
void get_primes(int n)
{
	for(int i = 2; i <= n; i++)
	{
		if(!st[i])
		{
			primes[cnt++] = i;
//			h[i] = true;	
		}
		 
		
		for(int j = 0; j < cnt && primes[j] <= n /i; j++)
		{
			st[i*primes[j]] = true;
			if(i%primes[j] == 0) break;	
		}	
	}	
} 

int main()
{
	get_primes(1000000);
	
	while(true)
	{
		scanf("%d", &n);
		if(!n) break;
		 
		int i = 0; 
		bool flag = false;
		while(primes[i] < n)
		{
//			if(h[n - primes[i]])
			if(!st[n - primes[i]]) // st[x] = false,表示x是质数 
			{
				printf("%d = %d + %d\n", n, primes[i], n - primes[i]);
				flag = true;
				break;	
			}
			i++;	
		}	
		if(!flag) printf("Goldbach's conjecture is wrong.\n");
		
	}
	
	return 0;
	
}

时间复杂度

参考文章

https://www.acwing.com/solution/content/22512/

/*
朴素筛:O(nlg(n)lg(n))
质数:不能是别的数的倍数--从2开始往上遍历每个数的倍数--标记为不能是质数
primes先把1-1e7的所有质数筛出来[3,5,7...]
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}
线性筛:
n 只会被 最小质因子筛掉
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;//如果当前数没被筛过 则把i这个数加进质数列表primes里 
        for (int j = 0; primes[j]*i<=n;j++)//从小到大枚举所有质数
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
1 i%primes[j]==0 primes[j]一定是i的最小质因子--(因为从小到大遍历j)primes[j]一定是primes[j]*i的最小质因子
2 i%primes[j]!=0 则primes[j]一定小于i的所有质因子--primes[j]也一定是primes[j]*i的最小质因子
对于一个合数x 假设primes[j] 是x的最小质因子 当i枚举到x/primes[j]时,则后面的合数给后面的质数去筛
        }
    }
}
欧拉线性筛的关键在于：每个合数只被它最大的非自身的因数筛掉。
例如：
12不会被4筛掉，而是被6筛掉；
45不会被9筛掉，而是被15筛掉。

当前用于筛素数的数i  被i筛掉的数  被i筛掉的数  被i筛掉的数  被i筛掉的数
2   2 * 2=4         
3   3 * 2=6     3 * 3=9     
4   4 * 2=8         
5   5 * 2=10    5 * 3=15    5 * 5=25    
6   6 * 2=12            
7   7 * 2=14    7 * 3=21    7 * 5=35    7 * 7=49
8   8 * 2=16            
9   9 * 2=18    9 * 3=27    (9 * 5=45)
10  10 * 2=20               |
...                         |
15  15 * 2=30   15*3 = 45  ←
我们以 12不被4筛掉而被6筛掉 为例：
当 i 循环执行到 i=4 时：
素数表prime中已有两个素数：2和3。
此时在check数组中已经被标记为1的数（合数）是：4、6、9。
因为i=4已经被标记为1，所以我们不将4添加进素数表prime。
此时执行 j循环：
因为素数表prime中有2和3，所以预计将要被筛掉的数是4×2=8 和 4×3=12。
当4×2=8被筛掉以后，经过 i mod prime[j]=0 判断可以知道4mod2=0，此时应结束j循环不再筛4×3=12。

j 循环到 i mod Prime[j]==0 就恰好需要停止的理由是：
下面用 s(smaller) 表示小于 j 的数[0,j)，L(larger) 表示大于 j 的数(j,n]。
1 i 的最小质因数肯定是 Prime[j]
（如果 i 的最小质因数是 Prime[s]，那么Prime[s] 更早被枚举到（因为我们从小到大枚举质数），当时就要break）
既然 i的最小质因数是 Prime[j]，那么 i × Prime[j] 的最小质因数也是 Prime[j]。所以，j本身是符合“筛条件”的。
2 i × Prime[s] 的最小质因数确实是 Prime[s]。
（如果是它的最小质因数是更小的质数 Prime[t]，那么当然 Prime[t] 更早被枚举到，当时就要break）
这说明 j 之前（用i×Prime[s]的方式去筛合数，使用的是最小质因数）都符合“筛条件”。
3 i × Prime[L] 的最小质因数一定是 Prime[j]。
（因为 i 的最小质因数是Prime[j]，所以i×Prime[L] 也含有Prime[j] 这个因数（这是 i 的功劳），
所以其最小质因数也是 Prime[j]（新的质因数Prime[L] 太大了））
这说明，如果 j继续递增（将以i×Prime[L] 的方式去筛合数，没有使用最小质因数），是不符合“筛条件”的。

举例
prime = [2,3,5,7...]
4 % prime[0] = 0 
1. 4的最小质因数 == prime[0] == 2
2. 
主要看第三种情况 prime[L]*i == 更大的i次*prime[j] 
3. 4*prime[1]=4*3=12 的最小质因数 = prime[0] = 2 所以可以在之后的i==6 时j==0 prime[j]==2时达到

9 % prime[1] = 0
1. 9的最小质因数 == prime[1] == 3
2. 9*prime[0] = 9*2 = 18的最小质因数 = prime[0] = 2 
主要看第三种情况 prime[L]*i == 更大的i次*prime[j] 
3. 9*prime[2] = 9*5 = 45的最小质因数 = prime[1] = 3 所以 可以在之后的i==15时 j==1 prime[j]==3时达到 
*/

作者：仅存老实人
链接：https://www.acwing.com/solution/content/22512/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。