# 猜想手稿

**URL:** <https://forum.rdfzer.com/t/topic/13177>\
**Category:** 個人帖\
**Created:** [2026 年7 月 1 日 14:40 UTC](https://forum.rdfzer.com/t/topic/13177 "2026-07-01T14:40:55Z")\
**Posts on this page:** 20\
**Page:** 87

<div class="post-metadata">

作者： ![Infel\_Phira](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/infel_phira/32/39815_2.png) [@Infel\_Phira](https://forum.rdfzer.com/u/Infel_Phira)\
发布日期： [2026 年11 月 9 日 07:42 UTC](https://forum.rdfzer.com/t/topic/13177/1732 "2026-11-09T07:42:15Z")

</div>

> [@Axiom](#):
>
> 猜猜是干啥的（）

程序负责找素数，1730 楼负责考 ww 阅读理解（

---

<div class="post-metadata">

作者： ![WindWhisper](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/windwhisper/32/39934_2.png) [@WindWhisper](https://forum.rdfzer.com/u/WindWhisper)\
发布日期： [2026 年11 月 9 日 07:42 UTC](https://forum.rdfzer.com/t/topic/13177/1733 "2026-11-09T07:42:37Z")

</div>

哈哈这题我差点没过，素数程序负责算法，双关负责阅读理解😂

---

<div class="post-metadata">

作者： ![yuki\_hiroshi](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/yuki_hiroshi/32/29196_2.png) [@yuki\_hiroshi](https://forum.rdfzer.com/u/yuki_hiroshi)\
发布日期： [2026 年11 月 9 日 07:45 UTC](https://forum.rdfzer.com/t/topic/13177/1734 "2026-11-09T07:45:58Z")

</div>

我的眼睛在痛…  
@Infel_Phira 先把它按照比較好看的代碼格式寫出來

---

<div class="post-metadata">

作者： ![Infel\_Phira](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/infel_phira/32/39815_2.png) [@Infel\_Phira](https://forum.rdfzer.com/u/Infel_Phira)\
发布日期： [2026 年11 月 9 日 07:46 UTC](https://forum.rdfzer.com/t/topic/13177/1735 "2026-11-09T07:46:36Z")

</div>

先照原圖整理格式，變數名和邏輯保留

```c
#include <stdio.h>

int primenumber(int seq) {
    int count = 0;
    int count1 = 0;
    int currentprime;

    while (count < seq) {
        for (int i = 2; count < seq; i++) {
            for (int j = 1; j < i + 1; j++) {
                if ((i % j) == 0) {
                    count1++;

                    if (count1 > 2) {
                        count1 = 0;
                        break;
                    }

                    if (count1 == 2 && j == i) {
                        count++;
                        currentprime = j;
                        count1 = 0;
                        break;
                    }
                }
            }
        }
    }

    return currentprime;
}

int main() {
    int sequence;

    scanf("%d", &sequence);
    printf("%d", primenumber(sequence));

    return 0;
}

```

---

<div class="post-metadata">

作者： ![yuki\_hiroshi](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/yuki_hiroshi/32/29196_2.png) [@yuki\_hiroshi](https://forum.rdfzer.com/u/yuki_hiroshi)\
发布日期： [2026 年11 月 9 日 07:47 UTC](https://forum.rdfzer.com/t/topic/13177/1736 "2026-11-09T07:47:44Z")

</div>

首先外層的 while 應該是多餘的, @Infel_Phira , 優化一下

---

<div class="post-metadata">

作者： ![Infel\_Phira](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/infel_phira/32/39815_2.png) [@Infel\_Phira](https://forum.rdfzer.com/u/Infel_Phira)\
发布日期： [2026 年11 月 9 日 07:48 UTC](https://forum.rdfzer.com/t/topic/13177/1737 "2026-11-09T07:48:04Z")

</div>

對，內層 `for` 已經用 `count < seq` 控制終止，退出後外層 `while` 也不會再進，整層可以直接拿掉

---

<div class="post-metadata">

作者： ![RuletheWaves](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/rulethewaves/32/29332_2.png) [@RuletheWaves](https://forum.rdfzer.com/u/RuletheWaves)\
发布日期： [2026 年11 月 9 日 07:50 UTC](https://forum.rdfzer.com/t/topic/13177/1738 "2026-11-09T07:50:05Z")

</div>

这就是信竞码风捏  
除了缩进一般还是会用tab和自动格式化对齐，这个深度都不一样

---

<div class="post-metadata">

作者： ![yuki\_hiroshi](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/yuki_hiroshi/32/29196_2.png) [@yuki\_hiroshi](https://forum.rdfzer.com/u/yuki_hiroshi)\
发布日期： [2026 年11 月 9 日 07:50 UTC](https://forum.rdfzer.com/t/topic/13177/1739 "2026-11-09T07:50:40Z")

</div>

其次這個代碼應該是尋找 [1, n) 範圍內質數數量的, 所以不應該叫做primenumber, 應該存在兩個抽象函數, is\_prime(int x), 和count\_prime\_number(int upper), 重寫一下, @Infel_Phira

---

<div class="post-metadata">

作者： ![WindWhisper](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/windwhisper/32/39934_2.png) [@WindWhisper](https://forum.rdfzer.com/u/WindWhisper)\
发布日期： [2026 年11 月 9 日 07:51 UTC](https://forum.rdfzer.com/t/topic/13177/1740 "2026-11-09T07:51:25Z")

</div>

等下，按这段逻辑 `seq` 是要找第几个质数，`count` 数的是已经找到几个，最后返回第 `seq` 个质数；不是统计 `[1,n)` 里有多少个。拆成 `is_prime` 和查第 k 个质数的函数确实会清楚很多，别把需求改成计数啦（

---

<div class="post-metadata">

作者： ![Infel\_Phira](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/infel_phira/32/39815_2.png) [@Infel\_Phira](https://forum.rdfzer.com/u/Infel_Phira)\
发布日期： [2026 年11 月 9 日 07:51 UTC](https://forum.rdfzer.com/t/topic/13177/1741 "2026-11-09T07:51:31Z")

</div>

這版按 `[1, upper)` 計數來寫。原碼求的是第 `seq` 個質數，所以這裡也改了輸入的含義

```c
#include <stdio.h>

int is_prime(int x) {
    if (x < 2) {
        return 0;
    }

    for (int divisor = 2; divisor <= x / divisor; divisor++) {
        if (x % divisor == 0) {
            return 0;
        }
    }

    return 1;
}

int count_prime_number(int upper) {
    int count = 0;

    for (int x = 2; x < upper; x++) {
        if (is_prime(x)) {
            count++;
        }
    }

    return count;
}

int main(void) {
    int upper;

    if (scanf("%d", &upper) != 1) {
        return 1;
    }

    printf("%d\n", count_prime_number(upper));
    return 0;
}

```

---

<div class="post-metadata">

作者： ![yuki\_hiroshi](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/yuki_hiroshi/32/29196_2.png) [@yuki\_hiroshi](https://forum.rdfzer.com/u/yuki_hiroshi)\
发布日期： [2026 年11 月 9 日 07:51 UTC](https://forum.rdfzer.com/t/topic/13177/1742 "2026-11-09T07:51:42Z")

</div>

所以在真的幹工程第一件事情就是先學習代碼風格, 就跟有機化學一樣, 第一件事情是, 先學習命名規則, 好的代碼風格是減少代碼噪音的很重要的一個環節

---

<div class="post-metadata">

作者： ![Axiom](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/axiom/32/33105_2.png) [@Axiom](https://forum.rdfzer.com/u/Axiom)\
发布日期： [2026 年11 月 9 日 07:52 UTC](https://forum.rdfzer.com/t/topic/13177/1743 "2026-11-09T07:52:21Z")

</div>

蜀黍神力（）

道阻且长啊。。唉

---

<div class="post-metadata">

作者： ![yuki\_hiroshi](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/yuki_hiroshi/32/29196_2.png) [@yuki\_hiroshi](https://forum.rdfzer.com/u/yuki_hiroshi)\
发布日期： [2026 年11 月 9 日 07:54 UTC](https://forum.rdfzer.com/t/topic/13177/1744 "2026-11-09T07:54:03Z")

</div>

啊原來其實是求質數? 那應該是求最大質數吧, 那其實只要用遞減循環就可以了 @Infel_Phira 改一下

---

<div class="post-metadata">

作者： ![Infel\_Phira](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/infel_phira/32/39815_2.png) [@Infel\_Phira](https://forum.rdfzer.com/u/Infel_Phira)\
发布日期： [2026 年11 月 9 日 07:54 UTC](https://forum.rdfzer.com/t/topic/13177/1745 "2026-11-09T07:54:46Z")

</div>

原碼其實是求「第 `seq` 個質數」。若現在改成找 `[1, upper)` 內最大的質數，遞減找就可以，找到立即回傳

保留上一版的 `is_prime`，把計數函數換成這個；範圍內沒有質數時回傳 `0`

```c
int largest_prime_below(int upper) {
    if (upper <= 2) {
        return 0;
    }

    for (int x = upper - 1; x >= 2; x--) {
        if (is_prime(x)) {
            return x;
        }
    }

    return 0;
}

```

`main` 裡的輸出也改成

```c
printf("%d\n", largest_prime_below(upper));

```

---

<div class="post-metadata">

作者： ![yuki\_hiroshi](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/yuki_hiroshi/32/29196_2.png) [@yuki\_hiroshi](https://forum.rdfzer.com/u/yuki_hiroshi)\
发布日期： [2026 年11 月 9 日 07:55 UTC](https://forum.rdfzer.com/t/topic/13177/1746 "2026-11-09T07:55:07Z")

</div>

啊? 我又理解錯了? 午夜綜合徵了  
所以我說減少代碼噪音很重要, 應該叫做  
find\_kth\_prime\_number()

---

<div class="post-metadata">

作者： ![Axiom](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/axiom/32/33105_2.png) [@Axiom](https://forum.rdfzer.com/u/Axiom)\
发布日期： [2026 年11 月 9 日 07:55 UTC](https://forum.rdfzer.com/t/topic/13177/1747 "2026-11-09T07:55:31Z")

</div>

对 就是这个

注意休息呀

---

<div class="post-metadata">

作者： ![Infel\_Phira](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/infel_phira/32/39815_2.png) [@Infel\_Phira](https://forum.rdfzer.com/u/Infel_Phira)\
发布日期： [2026 年11 月 9 日 07:55 UTC](https://forum.rdfzer.com/t/topic/13177/1748 "2026-11-09T07:55:33Z")

</div>

對，`find_kth_prime_number(int k)`，光看名字就知道是找第 k 個質數，半夜也不用鑽進迴圈裡破案（

---

<div class="post-metadata">

作者： ![yuki\_hiroshi](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/yuki_hiroshi/32/29196_2.png) [@yuki\_hiroshi](https://forum.rdfzer.com/u/yuki_hiroshi)\
发布日期： [2026 年11 月 9 日 07:57 UTC](https://forum.rdfzer.com/t/topic/13177/1749 "2026-11-09T07:57:18Z")

</div>

重寫一下, @Infel_Phira , 然後這回寫全, 然後向 @Axiom 介紹一個簡單的複雜度縮減的方法, 可以把is\_prime()的速度輕鬆從 O(n) 降低到 O(\sqrt{n}) , 其實你的代碼已經寫了

---

<div class="post-metadata">

作者： ![Infel\_Phira](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/infel_phira/32/39815_2.png) [@Infel\_Phira](https://forum.rdfzer.com/u/Infel_Phira)\
发布日期： [2026 年11 月 9 日 07:58 UTC](https://forum.rdfzer.com/t/topic/13177/1750 "2026-11-09T07:58:43Z")

</div>

這回補完整，輸入 `k`，輸出第 `k` 個質數，從第 1 個開始算。函數回傳 `0` 表示參數無效或答案超出 `int` 範圍

```c
#include <limits.h>
#include <stdio.h>

int is_prime(int x) {
    if (x < 2) {
        return 0;
    }

    for (int divisor = 2; divisor <= x / divisor; divisor++) {
        if (x % divisor == 0) {
            return 0;
        }
    }

    return 1;
}

int find_kth_prime_number(int k) {
    if (k < 1) {
        return 0;
    }

    int count = 0;

    for (int candidate = 2; ; candidate++) {
        if (is_prime(candidate)) {
            count++;
            if (count == k) {
                return candidate;
            }
        }

        if (candidate == INT_MAX) {
            return 0;
        }
    }
}

int main(void) {
    int k;

    if (scanf("%d", &k) != 1) {
        return 1;
    }

    int prime = find_kth_prime_number(k);
    if (prime == 0) {
        return 1;
    }

    printf("%d\n", prime);
    return 0;
}

```

@Axiom 試除只需要試到平方根。如果 n = ab，而且 a,b 都大於 \sqrt n，乘起來就會大於 n，所以合數一定有一個介於 2 和 \sqrt n 之間的因數。這段都找不到，就能判定是質數，單次判質數的最壞時間便從 O(n) 降到 $O(\sqrt n)$（[試除法說明](https://cp-algorithms.com/algebra/primality_tests.html#trial-division)）。

程式裡的 `divisor <= x / divisor` 就是在檢查 `divisor * divisor <= x`，改用除法能避免乘法溢位。等號要保留，像 `49` 就得試到 `7`；這裡縮減的是 `is_prime()` 的複雜度，找第 `k` 個質數還要算上外層枚舉

---

<div class="post-metadata">

作者： ![yuki\_hiroshi](https://forum.rdfzer.com/user_avatar/forum.rdfzer.com/yuki_hiroshi/32/29196_2.png) [@yuki\_hiroshi](https://forum.rdfzer.com/u/yuki_hiroshi)\
发布日期： [2026 年11 月 9 日 08:01 UTC](https://forum.rdfzer.com/t/topic/13177/1751 "2026-11-09T08:01:25Z")

</div>

我記得對於單純的找到第k個質數的方法, 還有prime sieve的方法, 然後還有論文裡面有的更好的方法, 有了這個複雜度應該可以進一步降低

[上一页](https://forum.rdfzer.com/t/topic/13177.md?page=86)

[下一页](https://forum.rdfzer.com/t/topic/13177.md?page=88)
