写在前面
基本问题
技巧
这类题需要预处理, 将处理好的素数数组作为全局变量, 可以节省一大部分时间.
全局变量初始化的便捷方法可以用 lambda, 算是一个不错的技巧了(在 C++中 main 函数之前执行的函数也用到了这一技巧), 即:
// global variable declare here
int _ = []{ // golbal variable need not capture in lambda
// init something...
return 0;
}();
这里给出预处理某一范围内的素数的通用模板: (欧拉筛法, 又称线性筛法)
constexpr int MX = 1e6;
int primes[MX], cnt{};
bitset<MX + 2> pri; // record
int _ = [] {
for (int i{2}; i <= MX; ++i) {
if (!pri[i])
primes[cnt++] = i;
for (int j{}; i * primes[j] <= MX; ++j) {
pri[i * primes[j]] = 1;
if (i % primes[j] == 0)
break;
}
}
return 0;
}();
题目
constexpr int MX = 5e6;
int primes[MX], cnt{};
bitset<MX + 2> pri; // record
int _ = [] {
for (int i{2}; i <= MX; ++i) {
if (!pri[i])
primes[cnt++] = i;
for (int j{}; i * primes[j] <= MX; ++j) {
pri[i * primes[j]] = 1;
if (i % primes[j] == 0)
break;
}
}
return 0;
}();
class Solution {
public:
int countPrimes(int n) {
int ans{};
for (int i{2}; i < n; ++i)
if (!pri[i])
++ans;
return ans;
}
};
2521. 数组乘积中的不同质因数数目 - 力扣（Leetcode）;
constexpr int MX = 1e3;
int primes[MX], cnt{};
bitset<MX + 2> pri; // record
int _ = [] {
for (int i{2}; i <= MX; ++i) {
if (!pri[i])
primes[cnt++] = i;
for (int j{}; i * primes[j] <= MX; ++j) {
pri[i * primes[j]] = 1;
if (i % primes[j] == 0)
break;
}
}
return 0;
}();
class Solution {
public:
int distinctPrimeFactors(vector<int>& nums) {
unordered_set<int> ans;
for (int num : nums) {
if (!pri[num])
ans.insert(num);
else {
for (int i{}; i < cnt && num > 1; ++i) {
if (num % primes[i] == 0)
ans.insert(primes[i]), num /= primes[i];
}
}
}
return ans.size();
}
};
素数对
题目
2761. 和等于目标值的质数对 - 力扣（Leetcode）;
2761. 和等于目标值的质数对 - 力扣（Leetcode）;特判情况参考了 0x3f 题解, 真的是每次都有新体验.
constexpr int MX = 1e6;
int primes[MX], cnt{};
bitset<MX + 2> pri; // record
int _ = [] {
for (int i{2}; i <= MX; ++i) {
if (!pri[i])
primes[cnt++] = i;
for (int j{}; i * primes[j] <= MX; ++j) {
pri[i * primes[j]] = 1;
if (i % primes[j] == 0)
break;
}
}
return 0;
}();
class Solution {
public:
vector<vector<int>> findPrimePairs(int n) {
if (n & 1) {
if (n > 4 && !pri[n - 2])
return {{2, n - 2}};
}
vector<vector<int>> ans;
for (int i{}; i < cnt; ++i) {
int x = primes[i];
int y = n - x;
if (y < x)
break;
if (!pri[y])
ans.push_back({x, y});
}
return ans;
}
};
2523. 范围内最接近的两个质数 - 力扣（Leetcode）;
constexpr int MX = 1e6;
int primes[MX], cnt{};
bitset<MX + 2> pri; // record
int _ = [] {
pri[0] = pri[1] = 1;
for (int i{2}; i <= MX; ++i) {
if (!pri[i])
primes[cnt++] = i;
for (int j{}; i * primes[j] <= MX; ++j) {
pri[i * primes[j]] = 1;
if (i % primes[j] == 0)
break;
}
}
return 0;
}();
class Solution {
public:
vector<int> closestPrimes(int left, int right) {
vector<int> ans{-1, -1};
int diff = 1e6;
for (int i{left}; i <= right; ++i) {
if (!pri[i]) {
for (int j{i + 1}; j <= right; ++j) {
if (!pri[j]) {
if (j - i < diff) {
diff = j - i, ans = {i, j};
if (diff == 2)
return ans;
}
break; // find one
}
}
}
}
return ans;
}
};