密码学大作业需要用到质数表，所以就把优雅的生成质数表作为我的第一个练习。标题叫优雅的生成质数表，不叫高效的生成质数表，所以只是用的最朴素的方法，尽可能把它写得好看，并不是最高效的生成质数表的方法。
什么是质数
生成质数表前先要知道什么是质数，不能被除了1和它本身整除的数叫质数，我还特地查了一下，0和1不是质数，所以先写一个谓词，判断是不是质数1
2
3
4
5
6
7
8
9constexpr bool is_prime(int n) {
if(n<2)return false;
if(n==2)return true;
if(n%2==0)return false;
for(int i=3;i*i<=n;i+=2)
if(n%i==0)
return false;
return true;
}constexpr是C++的一个关键字，用来表示这个函数可以在编译期计算，显然这个函数不依赖任何运行时提供的信息，是个可以在编译期计算的函数。
后面我们生成质数表都要依赖这个函数。
ranges简介
生成质数表我打算使用C++20的<ranges>库来写，这篇文章几乎就是为了这个而写的，使用视图和管道可以让代码显得非常简洁而优雅。下面简单说一下什么是视图和管道，以及几个常用的操作。
视图就像是一个空白的表格，在运行时才把数据填进去。说填其实不太准确，应该叫映射，视图不会存储任何数据，它是在运行时把实际存在的数据的引用映射到视图的对应位置，对视图的操作其实就是对数据的引用的操作，不会产生额外的拷贝开销。
管道的话名字已经很形象了，视图从左边流进去，处理成新的视图，从右边流出来。提到管道最重要的特性就是惰性求值。惰性求值就是只在需要用到这个数据的时候才去计算它的值。之前说过视图是个空的表格，在运行时才会填入数据，管道输出的视图一开始也是个空的表格，当我们的程序需要使用其中的某个值的时候，它才去计算那个位置的值，把它填进去。另外一些值得注意的就是，管道输出的数据是右值，如果管道的输入是右值的话会直接move过去，也不会产生拷贝开销。
所以，视图规定了数据的结构和顺序，管道规定了数据的计算和处理方式。
接下来说一下视图如何产生，C++标准库中的容器其实都可以隐式的转成视图，直接在后面加上管道运算符就可以当视图使用了。另外比较常用的就是std::views::iota(a,b)，这个是生成整数序列的,第一个参数设置初始值，第二个参数设置终止值（可以省略，省略就是无限序列），注意范围是左闭右开的，即生成的是[a,b)的整数序列。
接下来说一下管道操作有哪些，视图和管道之间通过|运算符连接，这个运算符就叫管道运算符，下面是常用的管道操作：
std::views::filter(pred)，表示用谓词pred过滤数据。std::views::transform(f)，表示对数据应用f。std::views::take(n)，表示取前n个数据。std::views::drop(n)，表示丢弃前n个数据。
接下来就用上面这些东西来生成质数表了。
生成质数表
最简单最容易想到的生成质数表的方式应该就是，对每个整数使用谓词判断是不是质数，也就是可以写成这样1
auto prime_seq=std::views::iota(1,11)|std::views::filter(is_prime);
下面是完整代码，运行的时候应该会输出1到10以内的质数1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
constexpr bool is_prime(int n) {
if(n<2)return false;
if(n==2)return true;
if(n%2==0)return false;
for(int i=3;i*i<=n;i+=2)
if(n%i==0)
return false;
return true;
}
int main() {
auto prime_seq=std::views::iota(1,11)|std::views::filter(is_prime);
std::ranges::copy(prime_seq,std::ostream_iterator<int>(std::cout," "));
return 0;
}
std::ranges::copy(prime_seq,std::ostream_iterator<int>(std::cout," "));是将质数序列拷贝到标准输出流。
或者可以有另一种表示方法，比如取大于10的10个质数，就可以这样写1
auto prime_seq=std::views::iota(11)|std::views::filter(is_prime)|std::views::take(10);
能否更优雅
大作业中需要的其实是随机选取一个质数，只是我想先生成质数表，然后从质数表中随机选取一个数，但是视图是不能通过下标来访问的，虽然可以通过drop丢弃前面的质数来选取指定位置的质数，但是这样写起来太麻烦了，所以需要一个get返回质数，或者把视图转成数组或者其他的能够通过下标访问的容器。
另一个问题，质数表是在编译期生成，还是在运行时惰性计算质数。显然只要我们在编译期指定需要生成的质数表的范围，是完全可以在编译期计算出整个表的，编译期计算出整个表的话就不需要在运行时再计算质数表，可以节省时间，但是需要保存整个表。如果使用惰性求值，，而不需要再计算后面的，但是还是会需要判断很多质数。
所以最后我还是决定写一个编译期版本的。
编译期生成质数表
虽然std::views::iota在范围确定之后是编译期可以完全计算的，但是std::views::filter会破坏编译期数量信息，所以不能使用filter，但是transform不会破坏编译期确定性，所以我们可以使用transform给每个数标上是否是质数，然后遍历一遍，用array保存质数表，下面是曲线救国的写法：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16template<int a, int b>
struct primes{
constexpr static auto seq=[]consteval{
constexpr auto v=iota(a,b)|transform([](int x){return pair{x,is_prime(x)};});
constexpr int size=count_if(v,[](auto p){return p.second;});
array<int,size>res{};
for(int i=0;auto[x,y]:v){
if(y){
res[i]=x;
i++;
}
}
return res;
}();
constexpr static int get(int n){return seq[n];}
};
consteval是强制只能在编译期计算，这样就保证seq一定是在编译期计算的。primes是一个模板结构体，有两个成员，seq和get。seq就是质数数组可以直接用下标访问第n个质数，get是一个函数，可以像使用函数一样获取第n个质数。
在支持静态分析的编辑器上应该能直接看到结果
一些使用上的优化
因为一般人应该不能够一眼看出一个区间里面有多少个质数，所以使用get很可能会越界，越界是未定义写为，可能给出错误的结果，也可能报运行时错误，这都是我们不希望看见的，至少我们希望程序的运行是可控的。所以我们可以把n对数组大小取模，这样起码可以保证一定能获取到合法的数。如果是对顺序要求很严格的人应该也不会输入越界的索引，所以也能获取到正确的结果，这样应该能应对大部分情况了。1
constexpr static int get(int n){return seq[n%seq.size()];}
同理，如果范围内没有质数的话，只要获取了肯定会报错，但是质数表是编译期内生成的，也就是说我们在编译的时候就可以知道这个表是不是空的了。生成空的质数表显然不是我们希望的，因为会在运行时访问的时候报错，但是我们可以通过静态断言，把这个报错提前到编译期，如果我们给定的范围内没有质数就报个编译期的错误，告诉写代码的人这个范围内没有质数。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17template<int a, int b>
struct primes{
constexpr static auto seq=[]consteval{
constexpr auto v=iota(a,b)|transform([](int x){return pair{x,is_prime(x)};});
constexpr int size=count_if(v,[](auto p){return p.second;});
static_assert(size>0, "No found primes");
array<int,size>res{};
for(int i=0;auto[x,y]:v){
if(y){
res[i]=x;
i++;
}
}
return res;
}();
constexpr static int get(int n){return seq[n%seq.size()];}
};static_assert就是静态断言，它要求size要大于0，如果编译到这里的时候size不大于0，那就会报错没有找到质数，就像这样
或者在支持静态分析的编辑器上也能看到报错了
结束
虽然生成seq的时候使用了for循环看起来不够优雅，但是我目前也还没有更好的写法在保持优雅的同时实现编译期计算。