algorithm - 更好的算法 - 下一个半素数

Question

Given n, find m such that m is the smallest semiprime greater than n.

下一个素数非常简单，半素数就没那么简单了。需要明确的是，只需要半素数，尽管同时获得这些因子会很方便。

我已经想到了一些方法，但我确信还有更好的方法。

假设算术运算为 O(1)。我使用了 Eratosthenes 筛法，它是 O(n log log n)，我知道 Atkin 筛法，但我喜欢我的半优化 Eratosthenes。

1。从n开始计数

从n开始往上数，找到一个半素数就停止。

这看起来真的很愚蠢，但如果有一个 O(log n) 半素数测试或 O(1) 测试给定下面的素数，这可能比其他 2 个更快。

半素数分布似乎比素数分布高得多，因此通过良好的半素数测试，这实际上可能比 O(n) 更好。

2。质数倒计时

定义 prev(x) 和 next(x) 并分别给出前一个和下一个质数，如果质数存储在树中或使用列表二分查找，则可以是 O(log n)。

先做筛子。

从 p=prev(sqrt(n)) 和 q=next(n/p) 开始。当 pq<=n 时，转到下一个 q。如果 pq 小于目前的最小值，则将其记录为新的最小值。继续前一个 p，直到用完 p 进行测试。

这可以保证找到正确答案，但速度相当慢。不过仍然是 O(n log n)，所以也许可以接受。

3。素数加数

像往常一样从筛子开始。为 O(1) 素数测试创建筛子的哈希集 View 。

从 p=2 开始。遍历素数直到 sqrt(n)。对于每个 p，得到 q=(((n/p+1)/2)*2)+1=(((n/p+1)>>1)<<1)|1。当 pq 小于目前的最小值并且 q 不是质数时，将 2 添加到 q。如果 pq 仍然小于最小值，则将其记录为新的最小值。

---

我在 Java 中实现了#1 和#3，它们都使用相同的埃拉托色尼筛法实现。大部分运行时间都花在筛选上，所以如果要进行优化，那就在筛选中。经过一些优化后，向上计数(#1)击败了素数向上计数(#3)，在最后一个最大测试(11 位十进制数字 n)中快了一倍。

但仍有希望，因为筛子需要扩展多远取决于要进行质数测试的最大数。如果存在具有较低素数测试界限的半素数测试，则计数方法可能会更快。

肯定有更好的算法？或者至少是一种更好的方法来实现这一点？

Answer 1

人们回答的问题略有不同，所以让我将其分成几个部分。

1. 是_semiprime(n)

给定一个值 n，它是否是一个半质数。对于微小的输入，我们当然可以预先计算并在 O(1) 或搜索中返回答案。在某些时候，我们会被存储需求压得喘不过气来。据我所知，这个问题没有非常有效的解决方案。它类似于素数或无平方测试，因为我们可以通过简单的可除性测试快速剔除大多数随机输入。假设我们有一个快速素数测试，其中包括一些预测试，并且大部分工作只是寻找一个小因子，然后返回余数是否为素数。对于没有小因数的数字，我们可以做一些因式分解(例如 Brent/Pollard Rho)或尝试除法到 n^(1/3)。

在我的 Macbook 上，对于 1e8 到 1e7+1e7 的范围，每个数字大约需要 0.4 微秒，而对于 1e16 到 1e16+1e7 的范围，每个数字需要不到 2 微秒。

对于大型半素数或准半素数，我不确定是否有比找到单个因子更好的解决方案。我们只需要 N^(1/3) 的试验除法，但有更有效的标准因式分解算法。一些实现包括 Charles Greathouse , mine ，还有很多在RosettaCode .

1. next_semiprime(n)

在 1e16，到下一个半素数的平均距离在 10 以下，很少超过 100。和以前一样，如果你想做预计算，使用内存，并且可以忽略或摊销设置时间，这个可以回答迅速地。但是，一旦超过小输入，这又会变得非常麻烦。

我不认为你可以通过一个简单的 while (1) { n++;如果(is_semiprime(n))返回n； } 假设一个好的 is_semiprime 例程。做一个完整的筛子对我来说要慢得多，但你的里程可能会有所不同。一旦你超过 ~25 位数字输入，它真的不会执行。您可以通过使用增加因子计数的素数幂进行部分筛选来稍微优化，这意味着我们只需要对明显不是半素数的结果运行完整测试。对我来说节省的时间不多，这是有道理的，因为我们只删除了一些本地模数。如果我们正在查看 1000 位输入，那么我认为部分筛选很有意义。

在我的 Macbook 上，next_semiprime 使用简单的 is_semiprime 方法从 1e8 开始连续调用 1e6 次，每次调用大约需要 2 微秒，从 1e16 开始每次调用需要 17 微秒。

1. 半素数(低，高)

有些回答好像是在思考这个问题。特别是当 low <= 4 时，筛子就是正确的答案。有针对 totients 和 moebius 范围的快速筛选方法，我希望您可以采用一种方法来适应全因子计数。

注意:编写良好的 SoE 比 SoA 更快，所以不要被推荐阿特金筛法的人分心，因为他们可能刚刚阅读了维基百科页面的前几段。当然，筛选、素性测试和预测试的实现细节会对结论产生影响。缓存数据的预期输入大小、模式和容忍度也是如此。