论如何实现随机素数

下文中，简记

[l, r]^p

表示区间

[l, r]

且

r \ge l \ge 2

比如我要一个函数 ll rdp(ll l, ll r)（typedef long long ll;）表示在区间

[l, r]^p

内随机一个素数。已经定义了函数 ll rdn(ll l, ll r) 表示区间

[l, r]

内随机整数。

一般写法是：

do {
    p = rdn(l, r);
} while (isprime(p));

其中 isprime 是质数检查（为了减少时间默认为 12 组基底的稳定 Miller-Rabin）。但是，数据一大，或者 rp 不佳，就会卡很久。

更好的方法是基于素数筛，令 prm[i] 表示 1-based 意义下第

i

个质数，sz[i] 表示

\le i

的质数个数，则有

prm[rdn(sz[l], sz[r])]

但是这样的缺点也很明显，就是容易内存爆炸。

所以，本蒟蒻在这里发出问题：如何在时间和空间都适合（例如：1s, 512 MB）的情况下随机出一个质数？

求问随机素数