注：挑战条目来自@大卫_伯纳姆在截止日期之前提交，但被我的电子邮件系统隔离。 我是在原始博客文章发表后才发现的。 我正在更新结果以反映基于新条目的更改。
感谢所有为挑战 2 提交代码的人。 评分是一项挑战，因为有些代码对于较小的值效果更好，而有些代码对于较大的值效果更好。 下表列出了挑战各部分的结果。 共有三轮比赛是素数、 1000 个不能被 5 整除的 5 位随机奇数、不能被 5 整除的 8 位和 9 位奇数、以及不能被 5 整除的 12 至 15 位奇数。 结果基于最后两个条件。 分数根据挑战进行分配，1.5 分英石, 1 换 2 ND , 3 时为 0.5 RD 。 还给出了最快提交的时间（以秒为单位）。
@leelaim isPrime(Small) 时间与 JMP 工作人员的速度一样快 (+3 分)。 @落在isPrime(Big) 脚本使用并行分配函数来提高速度。 其中两个条目缓存了其结果获取素数使用命名空间。 当需要多次访问结果时，此方法非常有用（但是，运行时间基于未缓存的结果）。 所有这四个条目都包含在下面。
这是两次挑战后的排行榜：
挑战 3 将于 6 月 1 日星期三发布。
挑战 2 要求以两种可能的方式寻找素数。 给定一个正整数值n ，你必须找到：1) n素数或 2) 以下所有素数n 。 让我们从 2) 开始，因为它更容易实现。 寻找素数的最简单方法是试除法。 从 2 作为候选数和一组空素数开始，检查当前素数集中是否有任何东西能整除候选数。 如果不是，则将其添加到素数集中并继续下一个候选。 由于素数集中没有任何内容可以开始，因此添加 2。 检查 3，它不会除以 {2} 中的任何内容，并且被添加到素数集中。 然而，数字 4 确实除掉了 {2,3} 中的某些内容，并且没有相加。 下面显示了一个示例实现。
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = [];
For(i=2,i<=n,i++,
For(j=2,j<=N Row(primeSet),j++,
If(Mod(i,j)==0, Break());
);
If(j>N Row(primeSet),primeSet = primeSet |/ i);
);
primeSet;
);
这种方法有一些优点：它易于理解，代码简洁，并且可以轻松适应素数查找挑战。 不幸的是，它非常慢。 查找 100,000 以下的素数我花了 19.43 秒。
稍微复杂一点的方法是使用筛子。 筛子不是测试数字是否为素数，而是测试数字是否为素数。 最古老和最著名的是埃拉托斯特尼筛法。 首先假设一切都是素数。 从第一个素数 2 开始，找到所有能整除它的数，并将它们从素数集中删除。 继续处理仍处于素数集中的下一个数字。 以下是未优化的版本。
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = J( n, 1, 1 );
primeSet[1] = 0;
For( i = 2, i <= n, i++,
For( j = i, j <= n / i, j++,
primeSet[j * i] = 0
)
);
Loc( primeSet );
);
最明显的优势是速度。 我查找 100,000 以下的所有素数的时间为 0.2811 秒，大约快了 70 倍，而查找 1,000,000 的素数则为 3.4025 秒。 代码还是简洁易懂的。 一个小缺点是您需要创建一个向量来跟踪非素数（也就是说，您不能通过连接来增长列表 - 我们稍后将看到这不一定是一个优点）。 这就造成了寻找的问题n素数更困难，因为您不确切知道需要多大的向量。
以下是两个优化版本。 第一个首先删除所有 2 的倍数，然后仅循环从 3 开始的奇数。 平方（ n ) 用于外循环的上限，因为所有小于该上限的非素数都已被筛出。 例如，要查找 100 以下的所有素数，只需筛选到 10。 任何大于 10 的素数的筛出数将是该素数乘以小于 10 的数的乘积，该数将与其他素数一起被删除（例如，11*5 被 5 的筛子删除， 11*9，带筛子为3等）。 这些改进将运行时间减少了一半以上，达到 1.3545。 第二个展示了使用 JSL 的矩阵运算作为内循环的优势，1,000,000 的时间为 0.01625，100,000,000 的时间为 2.6694，提高了近 100 倍！
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
For( i = 3, i <= Sqrt( n ), i+=2,
For( j = i, j <= n / i, j++,
primeSet[j * i] = 0
)
);
Loc( primeSet );
);
getPrimes2 = Function( {n}, {primeSet,i,j,upper},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
i = 3;
upper = Sqrt(n);
For(i=3,i<=upper,i+=2,
If(primeSet[i] == 1,
primeSet[(i*2)::n::i] = 0;
);
);
Loc( primeSet );
);
你能做得更好吗？ 这阿特金筛理论上效率更高，并在素数阿特金斯示例.JSL和普林斯阿特金斯（优化）.JSL 。 第一个给出了未优化且更易于理解的实现（1,000,000 需要 2.236 秒）。 比埃拉托色尼的非优化版本更好。 然而，优化版本无法击败优化的埃拉托斯特尼（100,000,000 耗时 4.914 秒）。 此外，它在程序上和理论上都更长、更复杂。
从数字表中读取怎么样？ 虽然这不符合编写算法的精神，但我并没有说你不能。 @Craige_Hales提供了使用这种方法的解决方案。 给定问题规范n不超过 1e8，包含压缩值的脚本大小需要超过 400 万个字符的代码、4.6MB 的磁盘空间和大约 5.5 秒的加载时间，无论大小如何n 。 比其他解决方案慢。 虽然既不是最快的也不是最短的，但我已经包含了 Craige 的脚本，因为他解决问题的独特方法、压缩的使用以及并行分配。
寻找n素数是一个更具挑战性的问题。 假设您使用筛子，您需要创建一个值向量，直到n th素数。 为此，需要估计该值的上限。 应避免低估，因为可能需要重新运行部分或全部算法才能找到未筛选的值。 第 n 个素数的估计值.jmp显示 6 种不同的估计。 EST1给出了小值被低估的情况n 。 许多估计仅适用于n大于特定值，在这些情况下需要小心提供替代估计值。 EST2有利于n ≥ 13 且EST3对于更大的值，可以对此进行改进。 不幸的是，好的界限很少是简单的。 EST4被用于Primes快速提交.jsl 。 虽然它做得不太好并且低估了非常大的值n ，简单易记。 EST5是使用非线性与实际值得出的。 EST6改进于EST5通过稍微扰动这些值，以便表中的任何值都不会被低估。 不保证 100 到 1e8 之间不存在低估。 其他表列给出了每种技术的低估/高估。
确定素数可以遵循与生成素数类似的路径。 给定一个数字X ，你可以让我= 2。 如果模（ n ,我） == 0停止，否则增加我。 继续直到模（ n ,我) == 0或者我== n 。 下面的代码受益于仅检查奇数我初次测试后我= 2 并停止时我> = 天花板(平方( n ）） 。
isPrime = Function({inVals},{i,j,outVec,nextVal,uBound},
outVec = J(N Row(inVals),1,-1);
For(i=1,i<=N Row(inVals),i++,
nextVal = inVals[i];
If(Mod(nextVal,2) == 0,
outVec[i] == 0;
,//ELSE
j = 3;
uBound = Ceiling(Sqrt(nextVal));
While(j < uBound & Mod(nextVal,j) != 0, j+=2);
If(j >= uBound, outVec[i] = 1,outVec[i] = 0);
)
);
outVec;
);
上面的脚本大约需要 1.4 秒来检查表中所有 1,000 个八位和九位数字大数表.jmp (小的）。
为了进一步改进这一点，您可以生成素数向量（最多天花板(平方( n ）） ）并迭代它们。
getPrimes = Function( {n}, {primeSet,i,j,upper},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
i = 3;
upper = Sqrt(n);
For(i=3,i<=upper,i+=2,
If(primeSet[i] == 1,
primeSet[(i*2)::n::i] = 0;
);
);
Loc( primeSet );
);
isPrime = Function({inVals},{i,j,outVec,primeVec,nextVal},
outVec = J(N Row(inVals),1,-1);
primeVec = getPrimes(Ceiling(Sqrt(Max(inVals))));
For(i=1,i<=N Row(inVals),i++,
nextVal = inVals[i];
j=1;
While(j < N Row(primeVec) & Mod(nextVal,primeVec[j]) != 0, j++);
If(j >= N Row(primeVec), outVec[i]=1,outVec[i]=0);
);
outVec;
);
这将时间缩短一半以上，降至 0.6 秒以下。
提高速度的两个一般注意事项：在需要多次使用矩阵值的情况下，使用变量而不是索引矩阵将该值分配给变量会更快。 虽然这可能会使代码更长，但会节省时间。 通过替换来尝试这个下一个值在上面的代码中及其索引矩阵值（ inVals[i] ）。 第二，洛克并且矩阵串联随着矩阵大小的增长而变慢。 如果您可以使用排序矩阵，本地排序执行二分搜索并且速度要快得多。看速度测试矩阵运算.jsl有关矩阵引用和串联的其他示例。
尝试在大数列中找到素数（大的）问题比较多。 找到前 10 个大约需要 1.9 秒。 此时，就必须依靠专门的算法来进行改进。 米勒-拉宾 (MR)是一种常用且相对容易实现的测试素性的技术。 确定性版本给出米勒拉宾1.jsl 。 MR 依赖于模幂运算，必须小心避免产生溢出错误。 MR 本身需要 5.28 秒才能完成所有 1000 个任务大的数字。 您可能会感到惊讶，MR 在处理以下问题时比上面的第一个 isPrime 算法（2.34 秒）慢小的数字。 这可能是因为随着数字大小的增加，它的计算效率变得更高，这表明了一种改进：使用上面的 2) 测试特定大小的素数。 如果该数字是质数，则停止。 否则，切换到 MR。这种方法可以在米勒拉宾2.jsl 。 进行了一些调整以找到要检查的理想素数数量。 这将时间缩短了一半，达到 2.33 秒。
