C语言实现从斐波那契数列中提取质数的代码优化方法

原代码问题梳理 #

• 存在硬编码限制：斐波那契存储数组固定长度为10、素数筛选循环写死执行7次，输入的上限n稍大就会出现数组越界、结果缺失的问题
• 逻辑冗余：不需要额外存储所有斐波那契数再统一筛选，生成斐波那契数的同时就可以直接判断是否为素数，省去不必要的数组空间占用
• 素数判断效率过低：当前逻辑遍历从1到数本身统计因数数量，实际只需遍历到该数的平方根，只要出现能整除的非1非自身值即可直接判定为非素数

优化后代码 #

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

// 单独封装素数判断函数，逻辑清晰可复用
bool is_prime(int num) {
    if (num <= 1) return false;
    if (num == 2) return true;
    if (num % 2 == 0) return false;
    for (int i = 3; i <= sqrt(num); i += 2) {
        if (num % i == 0) return false;
    }
    return true;
}

int main() {
    int n, t1 = 0, t2 = 1, next_term;
    printf("Input N= ");
    scanf("%d", &n);
    
    printf("Fibonacci List: ");
    // 兼容边界情况，输出符合要求的前两个斐波那契数
    if (n >= 0) printf("%d ", t1);
    if (n >= 1) printf("%d ", t2);
    
    printf("\nPrime numbers are: ");
    // 单独判断前两个斐波那契数中的素数
    if (is_prime(t1)) printf("%d ", t1);
    if (is_prime(t2)) printf("%d ", t2);
    
    next_term = t1 + t2;
    while (next_term <= n) {
        printf("%d ", next_term);
        // 生成一个斐波那契数就直接判断是否为素数
        if (is_prime(next_term)) {
            printf("%d ", next_term);
        }
        t1 = t2;
        t2 = next_term;
        next_term = t1 + t2;
    }
    
    return 0;
}

编译时如果使用gcc编译器，需要添加-lm参数链接数学库，示例命令：gcc fib_prime.c -o fib_prime -lm

优化说明 #

• 拆分素数判断为独立函数，逻辑解耦，代码可读性大幅提升
• 去掉冗余数组存储和硬编码限制，支持任意合法的n输入，不会出现越界问题
• 素数判断逻辑优化：提前排除偶数、仅遍历到平方根，运行效率提升数倍
• 生成斐波那契数的同时完成素数判断，仅需一次遍历即可完成全部逻辑，流程更简洁

内容的提问来源于stack exchange，提问作者iCitizen