Try   HackMD

2022q2 Homework (quiz5)

contributed by <ray90514>

測驗一

依照程式碼,主循環如下

  1. 判斷該迴文數長度是否為偶數,如果是該數必不為質數,找出下一個長度為奇數的迴文數
  2. 判斷是否為 3 或 5 的倍數,判斷是否為質數
  3. 求出下一個迴文數

判斷 3 和 5 的倍數有比較直接的方法,判斷質數則要先產生一個質數表,然後看質數表中的質數能否被該數整除。質數表的產生使用 Sieve of Eratosthenes 搭配 bitset 產生出小於等於

sqrt(n)。因為偶數除了 2 一定不是質數,只要記錄奇數就好。 以 bitset 儲存的質數表第 n 位為 0 代表 2n + 1 是質數,使用時先將質數表取反搭配 __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 位的新迴文數。

改進

測驗二

tags: linux2022