如何用指定链表结构体实现C语言kPrimes并解决超时问题

你遇到的核心问题有两个：质因数计数的性能瓶颈（导致超时）和Codewars提供的链表结构的正确使用。下面一步步帮你解决：

一、先解决性能问题：用筛法预计算质因数总个数 #

你的本地代码可能用了暴力试除法统计每个数的质因数个数，这种方法在处理大区间时会非常慢，直接导致Codewars超时。我们改用基于最小质因数的筛法，一次遍历就能高效计算出所有数的质因数总个数（包括重复的质因数，比如4=2×2计数为2），时间复杂度为O(n log log n)，性能提升非常明显。

辅助函数：计算质因数总个数数组 #

这个函数会生成一个数组，每个索引对应的值是该数的质因数总个数：

static int* compute_factor_counts(int max_num) {
    if (max_num < 2) return NULL;

    // 存储每个数的最小质因数
    int* min_prime = (int*)malloc((max_num + 1) * sizeof(int));
    // 存储每个数的质因数总个数
    int* factor_count = (int*)calloc(max_num + 1, sizeof(int));
    
    if (!min_prime || !factor_count) {
        free(min_prime);
        free(factor_count);
        return NULL;
    }

    // 初始化最小质因数数组：每个数的最小质因数初始化为自身
    for (int i = 0; i <= max_num; i++) {
        min_prime[i] = i;
    }

    // 筛法求最小质因数
    for (int i = 2; i * i <= max_num; i++) {
        if (min_prime[i] == i) { // i是质数
            for (int j = i * i; j <= max_num; j += i) {
                if (min_prime[j] == j) {
                    min_prime[j] = i;
                }
            }
        }
    }

    // 动态规划计算质因数总个数
    factor_count[0] = factor_count[1] = 0;
    for (int i = 2; i <= max_num; i++) {
        if (min_prime[i] == i) { // 质数的质因数个数为1
            factor_count[i] = 1;
        } else {
            // 非质数的质因数个数 = 它除以最小质因数后的数的个数 +1
            int p = min_prime[i];
            factor_count[i] = factor_count[i / p] + 1;
        }
    }

    free(min_prime);
    return factor_count;
}

二、正确使用Codewars提供的链表结构 #

Codewars给的链表工具函数已经帮你封装了创建、插入、反转、释放的逻辑，我们只需要按规则使用：

1. 用createList()创建空链表
2. 遍历区间时，符合条件的数用insertFirst()插入链表头部（因为头部插入效率高）
3. 遍历完成后用reverse()反转链表，得到从小到大的顺序
4. 记得释放临时分配的内存

完整实现kPrimes函数 #

struct list* kPrimes(int k, int start, int nd) {
    // 边界情况处理：区间无效或k小于1，返回空链表
    if (start > nd || k < 1) {
        return createList();
    }

    int max_num = nd;
    if (max_num < 2) {
        return createList();
    }

    // 获取质因数计数数组
    int* factor_count = compute_factor_counts(max_num);
    if (!factor_count) {
        return createList();
    }

    struct list* result = createList();
    // 遍历区间，将符合条件的数插入链表头部
    for (int num = start; num <= nd; num++) {
        if (factor_count[num] == k) {
            insertFirst(result, num);
        }
    }

    // 反转链表，得到从小到大的正确顺序
    result = reverse(result);

    // 释放临时数组内存
    free(factor_count);
    return result;
}

关键说明 #

• 为什么用头部插入+反转？因为insertFirst是O(1)操作，比尾部插入（需要遍历链表）效率高，最后反转一次就能得到正确的顺序。
• 筛法的优势：不管区间多大，只需要一次预计算就能得到所有数的质因数个数，避免了对每个数单独暴力分解的重复计算，彻底解决超时问题。
• 内存安全：所有动态分配的内存都做了释放处理，避免内存泄漏。

测试你给出的例子countKprimes(5, 500, 600)，这个实现会正确返回[500, 520, 552, 567, 588, 592, 594]，并且不会超时。

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