algorithm - 添加数字的单个数字的最有效方法

Question

我正在研究一种算法来确定给定数字是否为质数并遇到了这个 website .但后来我想尝试自己的逻辑。我可以很容易地消除以 2、4、5、6、8 结尾的数字(对于 5 以上的数字以 0 结尾)，所以我剩下 1、3、7 和 9 作为可能的最后一位数字。现在，如果最后一位是 3，我可以将各个数字相加以检查它是否可以被 3 整除。我不想执行模数 (%) 运算并添加它们。有没有更有效的方法来对十进制数中的数字求和？也许使用按位运算...？

Answer 1

% 或模数运算符比添加单独的数字更快。但如果您真的想这样做，您可以部分展开循环，以自动转义 3 的倍数。

例如:

2 is prime
3 is prime
candidate = 5
while(candidate <= limit - 2 * 3)  // Unrolling loop for next 2 * 3 number
{
  if ( CheckPrime(candidate) ) candidate is prime;
  candidate += 2;
  if ( CheckPrime(candidate) ) candidate is prime;
  candidate += 4;  // candidate + 2 is multiple of 3 (9, 15, 21 etc)
}
if(candidate < limit) CheckPrime(candidate);

在上述方法中，我们消除了 3 的倍数，而不是通过添加数字来检查 3 的整除性。

你的观察很好。顺便说一句，它叫做wheel factorization找到质数。我已经为 wheel size = 6 (2*3) 做了，但您也可以为更大的车轮尺寸做同样的事情，例如:30(2*3*5)。上面的代码片段也称为所有质数都是 6N±1 类型。 (因为6N+3是3的倍数)

附注并非所有以 2 和 5 结尾的数字都是合数。 2 号和 5 号是异常(exception)。