U658905 【模板】素数筛法优化
题目背景
为了卡掉非正解线性筛,让正解埃氏筛通过(倒反天罡不是),特出此题。
建议使用分段筛(埃氏筛分块),但经过其他优化的筛法也可能可以通过。
原题:[P3383 【模板】线性筛素数](https://www.luogu.com.cn/problem/P3383)。
**请注意,本题在数据范围以及输出答案的方式上与原题有极大不同,请仔细阅读题面。**
题目描述
**这是一个交互题。**
你需要在程序内实现以下函数:
```cpp
extern "C" int *make()
```
该函数需要处理出 $10^9$ 内的所有质数,储存在一个 `int` 数组中,返回指向数组开头地址的指针。
交互库将假定第一个质数储存在返回数组下标为 $0$ 的位置上。
**请注意,你不需要,也不应该实现主函数。**
在一个测试点内,保证交互库会恰好调用你的函数一次。
输入格式
无
输出格式
无
说明/提示
本题只有一个测试点,出题人的权限为普通用户,只能把时间限制和空间限制开到 5s,512MB,空间可能不太够,省着用吧。
:::info[示例代码(然而因为没有经过太多优化不能通过)]
```cpp
#include
using namespace std;
constexpr int N = 1000000010,P = 51000000;
/*请注意,由于是交互题,并没有输入,你需要在程序内指定 n 的大小*/
bitset is_prime;
int prime[P],ptop;
extern "C" int *make()
{
is_prime.set();
is_prime[0] = is_prime[1] = false;
ptop = 0;
for(int i = 2;i * i