algorithm - 能被17整除的数？

Question

给定最多 1000 位的大量正数。您必须找出该数字是否可以被 17 整除。我知道一种算法，它说将最后一位数字乘以 5 并从剩余数字中减去，如果所得数字可被 17 整除，则该数字可被 17 整除。有没有更有效的方法？

Answer 1

你可以做的是遍历数字，跟踪当前值 modulo 17。当你到达最后时，如果当前值 modulo 17 是零，则为 17 的倍数；否则，不是。

例如，如果您的号码是 "12345"(我假设您将此号码存储在十进制字符串中？)，那么步骤是:

• 从0开始
• (0 * 10 + 1) mod 17 → 1
• (1 * 10 + 2) mod 17 → 12
• (12 * 10 + 3) mod 17 → 4
• (4 * 10 + 4) mod 17 → 10
• (10 * 10 + 5) mod 17 → 3

所以 12345 mod 17 是 3:12345 不能被 17 整除。

(当然，对于 12345，您可以只写 12345 mod 17 开始，但是对于大量的数字，上述方法让我们只处理一点点一次，这很方便，因为这意味着我们所有的数字都足够小以适合处理器的 native 32 位或 64 位整数。)