contributed by <ray90514
>
依照程式碼,主循環如下
判斷 3 和 5 的倍數有比較直接的方法,判斷質數則要先產生一個質數表,然後看質數表中的質數能否被該數整除。質數表的產生使用 Sieve of Eratosthenes 搭配 bitset 產生出小於等於 __builtin_ctzll
即可快速找到質數表中的質數。
/* Check if a number is prime. */
static bool isprime(const ull val)
{
if (!(val & 0x1)) /* Test for divisibility by 2 */
return false;
ull *pquadbits = (ull *) psieve;
ull next = 3; /* start at 7 (i.e. 3 * 2 + 1) */
for (ull quad = ~*pquadbits & ~0b111, prev = 0; prev <= half_max;
quad = ~*++pquadbits) {
if (!quad) {
prev += 64;
continue;
}
while (quad) {
ull i = EXP1;
next = prev + i;
if (!(val % ((next << 1) + 1)))
return false;
quad &= EXP2;
}
prev += 64;
}
return true;
}
使用上將質數表以 ull 為單位存取,根據前面之敘述以及 val % ((next << 1) + 1)
可以得出 next 就是第 n 位的 n ,也就是說 prev + i
為當前要找的質數的位數, prev
是之前已找的位數,則 i
是下一個質數在當前存取的 quad
的第幾位,也就是最低位的 1 在第幾位,用 __builtin_ctzll(quad)
求得。判斷完該質數後要將 quad
中該位清除,所以 EXP2
為 ~(1ULL << i)
。
產生下一個迴文數的方式為,依照前一個迴文數,修改其中某一位數及對稱的位數,從 0 到 9 ,直到每一位都不能被修改則產生 len + 1 位的新迴文數。
linux2022