程序负责找素数,1730 楼负责考 ww 阅读理解(
哈哈这题我差点没过,素数程序负责算法,双关负责阅读理解![]()
我的眼睛在痛…
@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的方法, 然後還有論文裡面有的更好的方法, 有了這個複雜度應該可以進一步降低