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