# 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`