计算最近的素数到另一个数字没有数组

Question

我有这个功课，但我不能完成它，因为我只能使用关系运算符和if-else/while，我不能使用库和方法，只有关系运算符和If或while时，我开始检查如果限制的数字是素数，首先检查If/by 2 3 5 7和11是否我用数字的平方根之前的每个数字尝试百分比（以确定它是否为是总理），但它只需要很多时间来做到这一点，我怎么能用更少的时间来计算它，对于英语是一个难得的解释抱歉。

Answer 1

没有阵列，唯一的另一种选择是有一些Eratosthenes筛选器（对于任何希望比试验部门有更好的复杂性比原始性测试），我知道的是懒惰列表，它可以模拟发电机。在伪代码，

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，在围棋，here（和a faster one），尽管它实现的\ S（链没有∪ S），

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

这可能是干脆做一个容易的事情。

该∪ s虽然可以安排in a tree，为额外的complexity advantage。也许是一个有趣的项目。