我想减少素数测试中的计算负载。目前我的循环只是测试赔率,如下所示:
for (k=3; k<=end; k+=2) {
我读到除了 2 和 3 之外的每个素数都是 k= 6 +/- 1 的函数。通过仅测试 2/3 的可能性,我可以将计算负载减少 33%。我能想到的唯一方法是振荡计数器以递增 2,然后是 4,然后是 2,然后是 4,每次迭代,例如测试 5、7、11、13 等。
有没有办法告诉循环这样做?还有另一种我不考虑的方法吗?
PS我知道筛法测试
我想减少素数测试中的计算负载。目前我的循环只是测试赔率,如下所示:
for (k=3; k<=end; k+=2) {
我读到除了 2 和 3 之外的每个素数都是 k= 6 +/- 1 的函数。通过仅测试 2/3 的可能性,我可以将计算负载减少 33%。我能想到的唯一方法是振荡计数器以递增 2,然后是 4,然后是 2,然后是 4,每次迭代,例如测试 5、7、11、13 等。
有没有办法告诉循环这样做?还有另一种我不考虑的方法吗?
PS我知道筛法测试
使用while
循环,而不是:
k = 3;
odd = false;
while( k<=end ) {
k += odd ? 2 : 4;
odd = !odd;
}
像这样的东西?
oscillate = false;
k = 3;
while(k <= end)
{
testForPrimes(k);
k += oscillate ? 2 : 4;
oscillate != oscillate;
}
就是图个好玩儿...
for (var k=3,l=0; k<=end; k+=2*(l%2+1),l++){ }