java - 计算与另一个数字最接近的素数，无需数组

Question

我有这个作业，但我无法完成它，因为我只能使用关系运算符和if-else/while，我不能使用库和方法，只能使用关系运算符和If或while，我开始检查作为限制的数字是否是素数，首先检查If/by 2 3 5 7和11，然后我尝试对数字平方根之前的每个数字进行％(以确定它是否是素数)，但它只是需要很多时间来做到这一点，如何我能用更少的时间计算更多吗，抱歉英语和罕见的解释。

Answer 1

没有数组，据我所知，拥有某种埃拉托色尼筛子的唯一其他选择(对于任何希望比通过试除进行素性测试具有更好复杂性的人来说)是使用惰性列表，它可以用生成器进行模拟。在伪代码中，

primes = [2..] \ [[p*p, p*p+p, ...] for p in primes]

以此为起点

primesFrom n = [n..] \ unionAll(
                    [[s,s+p..] for each p in psq
                               where psq = primes upto (2 * sqrt(n)),
                               where s   = div(n+p-1, p) * p] )

我们只需要它产生的第一个数字。这里的联合当然是一个有序联合，考虑到有序，增加来源，以有序方式产生结果，从较小的值到较大的值一个接一个。

使用两倍平方根，最大的 prime gap范围内被覆盖。您可以通过查找范围内素数间隙的精确值来使其更加精确。 psq 素数可以通过试除法找到，也可以在生成器中一一求出。

但是现在您需要以某种方式在某个地方维护这个生成器集合[s,s+p..]，并且仍然禁止使用数组。

链表是一种可能性。它也可以通过嵌套递归函数进行模拟，每个函数中都带有本地静态存储 closures ，在初始化时创建它们的链，例如

           = [n..] \ 
              ( [s1,s1+p1..] ∪
                ( [s2,s2+p2..] ∪
                  ( [s3,s3+p3..] ∪ (.... [sk,sk+pk..] ....))))

您可以看到 something just like this 的示例，在 Go 中，here (和 a faster one )，尽管它实现了 \ 链(没有 ∪ )，

   = (((....( [n..] \ 
                [s1,s1+p1..] ) \
                  [s2,s2+p2..] ) \
                    [s3,s3+p3..] ) \  ....) \ [sk,sk+pk..] 

这可能是一件更容易做的事情。

∪可以排列in a tree ，额外的complexity advantage 。也许是一个值得涉足的有趣项目。