欧拉计划 Project Euler60（素数对集合）题解

题干

思路

先欧拉筛预处理出素数，然后dfs，注意剪枝，不然太容易炸了

code

//13 5197 5701 6733 8389 
//26033
#include <bits/stdc++.h>using namespace std;using ll = long long;bool isprime(ll x) {if (x < 2) return false;for (ll i = 2; i * i <= x; ++i) {if (x % i == 0) return false;}return true;
}// 检查两个数拼接后是否是素数
bool check(ll a, ll b) {string s1 = to_string(a) + to_string(b);string s2 = to_string(b) + to_string(a);return isprime(stoll(s1)) && isprime(stoll(s2));
}// Euler筛提前先筛选一部分素数
vector<int> generatePrime(int li) {vector<int> pris;bool vis[li + 1];memset(vis, true, sizeof(vis));for (int i = 2; i < li; ++i) {if (vis[i]) pris.push_back(i);for (int p : pris) {if (i * p >= li) break;vis[i * p] = false;if (i % p == 0) break;}}return pris;
}// dfs 找满足条件的素数
void dfs(vector<int> &pris, vector<int> cur, int idx, int &minsum, vector<int> &ans) {if (cur.size() == 5) {int sum = 0;for (int p : cur) {sum += p;}if (sum < minsum) {minsum = sum;ans = cur;}return ;}for (int i = idx; i < pris.size(); ++i) {bool flag = true;for (int p : cur) {if (!check(p, pris[i])) {flag = false;break;}}if (flag) {cur.push_back(pris[i]);dfs(pris, cur, i + 1, minsum, ans);cur.pop_back();}}
}void solve() {int li = 10000;vector<int> pris = generatePrime(li);vector<int> cur, ans;int minsum = INT_MAX;dfs(pris, cur, 0, minsum, ans);for (int p : ans) {cout << p << " ";}cout << "\n";cout << minsum << "\n";}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1; // cin >> tt;while (tt--) {solve();}return 0;
}