简简单单的质数（复习）

加强一下质数学习，用线性筛选法降低时间复杂度，提高效率 

1.纯质数

题目链接：竞赛中心 - 蓝桥云课 (lanqiao.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 20210605; // 质数生成范围int primes[N], cnt;  // primes[]存储所有的质数,cnt质数数量
bool st[N];         // st[x]表示 x 是否被标记（存储的是非质数）// 线性筛法生成质数(直接用模板)
void get_primes(int n)
{for (int i = 2; i <= n; i++){if (!st[i]) primes[cnt++] = i;for (int j = 0; primes[j] <= n / i; j++){st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}
}// 检查一个数是否是质数
bool is_prime(int x)
{if (x < 2) return false;if (x < N) return !st[x];return false;
}//数位拆分
int fun(int y)
{int sign=0;while(y){sign=y%10;y/=10;if(!is_prime(sign)){return 0;}}return 1;
}int main()
{int sum=0;get_primes(20210605);for(int i=0; i<cnt; i++){sum+=fun(primes[i]); }cout<<sum<<endl;return 0;
}

2.哥德巴赫猜想

题目链接：E-哥德巴赫猜想_河南萌新联赛2024第（五）场：信息工程大学 (nowcoder.com) 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 50010; // 质数生成范围
int t;int primes[N], cnt;  // primes[]存储所有的质数
bool st[N];         // st[x]表示 x 是否被标记（存储的是非质数）// 线性筛法生成质数(直接用模板) 
void get_primes(int n)
{for (int i = 2; i <= n; i++){if (!st[i]) primes[cnt++] = i;for (int j = 0; primes[j] <= n / i; j++){st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}
}// 检查一个数是否是质数
bool is_prime(int x)
{if (x < 2) return false;if (x < N) return !st[x];return false;
}int main()
{get_primes(50000);cin >> t;while (t--){int n;cin >> n;bool found = false;for (int i = 0; i < cnt; i++){for (int j = i; j < cnt; j++){int temp = n - primes[i] - primes[j];if (temp > 0 && is_prime(temp) && temp >= primes[j]){cout << primes[i] << " " << primes[j] << " " << temp << endl;found = true; break; }}if (found){break;}}if (!found){cout << -1 << endl;}}return 0;
}