猜想手稿

程序负责找素数,1730 楼负责考 ww 阅读理解(

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

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

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

#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;
}

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

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

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

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

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

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

#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;
}

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

蜀黍神力()

道阻且长啊。。唉

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

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

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

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 裡的輸出也改成

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

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

对 就是这个

注意休息呀

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

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

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

#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)$(試除法說明)。

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

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