study
bitset<N> b;
b.count();
b.size();
b.test(); // 可检查二进制串的任意一位是 0 还是 1
b.none();
b.any();
b.all();
b[a] // 可以访问任意位元素,有越位可能
b.filp(); // flip函数传参数时,用于将参数位取反,flip函数不指定参数时,将bitset每一位全部取反
b.set(); // 将参数位置为1,规则如上
b.reset(); // 将参数位置为0,规则如上
b.set(a, c); // 指定两位参数时,将第一参数位的元素置为第二参数的值
b.to_数据类型 // 将bitset转换成某种数据类型,例如,string s = b.to_string();
7 个数据点
$bitset$优化埃氏筛
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<bitset>
using namespace std;
const int N = 1e7 + 10, MX = 1e8 + 10;
int n, m;
int p[N];
bitset<MX> vis;
void init(int n)
{
vis.set();
vis[0] = vis[1] = 0;
for (int i = 2; i * i <= n; i ++ )
if (vis[i]) {
for (int j = i << 1; j <= n; j += i) vis[j] = 0;
}
for (int i = 2; i <= n; i ++ ) if (vis[i]) p[ ++ m] = i;
}
int main()
{
scanf("%d", &n);
init(7000000);
for (int i = 1; i <= m; i ++ )
{
if (p[i] == n)
for (int j = max(1, i - 3); j <= min(i + 3, m); j ++ )
if (abs(p[i] - p[j]) == 6)
{
printf("Yes\n%d", p[j]);
return 0;
}
if (p[i] > n)
for (int j = max(1, i - 3); j <= min(i + 3, m); j ++ )
{
if (p[i] - p[j] == 6)
{
printf("No\n%d", p[j] > n ? p[j] : p[i]);
return 0;
}
else {
printf("No\n%d", p[i]);
return 0;
}
}
}
}
7 个数据点
线性筛
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<bitset>
using namespace std;
const int N = 1e7 + 10, MX = 1e8 + 10;
int n, m;
int p[N];
bool v[MX];
void init(int n)
{
// 质数从 2 开始出现
for (int i = 2; i <= n; i ++ )
{
if (!v[i]) p[ ++ m] = i; // 没有被更小的质因子标记过,所以为质数
for (int j = 1; p[j] * i <= n; j ++ ) // 通过质因子标记合数,不能大于上界 n
{
v[i * p[j]] = true; // 标记为合数
if (i % p[j] == 0) break;
// 此时 p[j] 为 i 的一个质因子,也就是存在一个 t,满足 p[j] * t == i
// 因为要求每个合数仅被它的最小素因子筛去正好一次,i 的质因数若小于 p[j],
// 就不满足为最小质因数,所以直接退出
}
}
}
int main()
{
scanf("%d", &n);
init(7000000);
for (int i = 1; i <= m; i ++ )
{
if (p[i] == n)
for (int j = max(1, i - 3); j <= min(i + 3, m); j ++ )
if (abs(p[i] - p[j]) == 6)
{
printf("Yes\n%d", p[j]);
return 0;
}
if (p[i] > n)
for (int j = max(1, i - 3); j <= min(i + 3, m); j ++ )
{
if (p[i] - p[j] == 6)
{
printf("No\n%d", p[j] > n ? p[j] : p[i]);
return 0;
}
else {
printf("No\n%d", p[i]);
return 0;
}
}
}
}
原因
$bitset$优化埃氏筛效率不够高,线性筛可储存数据范围不够大,但若用$bitset$优化,则效率不够高。
AC
试除法,
根据上面的代码,我们可以用线性筛计算所有性感质数的最大距离。
验证可行。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return false;
return true;
}
int main()
{
int n;
cin >> n;
for (int i = n - 6; i <= n + 6; i += 12)
if (is_prime(i) && is_prime(n))
{
cout << "Yes" << endl;
cout << i << endl;
return 0;
}
for (int i = n + 1;; i ++ )
if (is_prime(i) && (is_prime(i - 6) || is_prime(i + 6)))
{
cout << "No" << endl;
cout << i << endl;
return 0;
}
return 0;
}