为什么这两种采样素数的方法运行一样长？

Question

所以我实现了自己的 RSA 小算法，并在此过程中编写了一个函数来查找大素数。
首先，我编写了一个函数 prime? 来测试素数，然后我编写了两个版本的素数搜索函数。在第一个版本中，我只是测试随机的 BigIntegers，直到我遇到素数。在第二个版本中，我对一个随机的 BigInteger 进行采样，然后递增它直到找到一个素数。

(defn resampling []
  (let [rnd (Random.)]
    (->> (repeatedly #(BigInteger. 512 rnd))
         (take-while (comp not prime?))
         (count))))

(defn incrementing []
  (->> (BigInteger. 512 (Random.))
       (iterate inc)
       (take-while (comp not prime?))
       (count)))

(let [n 100]
  {:resampling   (/ (reduce + (repeatedly n resampling)) n)
   :incrementing (/ (reduce + (repeatedly n incrementing)) n)})

运行此代码产生重采样函数的两个平均值 332.41 和递增函数的 310.74。
现在第一个数字对我来说完全有意义。 prime number theorem 表示第 n 个素数的大小约为 n*ln(n)（其中 ln 是自然对数）。所以相邻素数之间的距离约为n*ln(n) - (n-1)*ln(n-1) ≈ (n - (n - 1))*ln(n) = ln(n)（对于nln(n) ≈ ln(n - 1)的大值）。由于我正在对 512 位整数进行采样，因此我希望素数之间的距离在 ln(2^512) = 354.89 附近。因此，随机抽样平均需要尝试 354.89 次才能达到质数，结果非常好。
令我困惑的是，为什么递增函数的步数几乎一样多。如果我想象在质数间隔 355 个单位的网格上投掷飞镖，平均应该只需要大约一半的步数就可以走到下一个更高的质数，因为平均而言我会击中两个质数之间的中心。

(prime?的代码有点长，大家可以看看here。)

Answer 1

你假设素数是均匀分布的，但事实似乎并非如此。

让我们考虑以下可能的情况：如果质数总是成对出现，例如 10...01 和 10...03，那么下一对将出现在 2*ln(n) 中。对于采样算法，这个分布没有区别，但是对于递增算法，从这样的对开始的概率几乎为 0，所以这意味着它需要平均走一半的大距离，即 ln(n).

简而言之：要正确估计增量算法的行为，仅知道素数之间的平均距离是不够的。

为什么这两种采样素数的方法运行一样长？

Why do these two methods of sampling primes run equally long?

java

random

primes

clojure