生成指定数两侧各p个质数并求平均值的C代码时间复杂度优化问询

我需要实现一个函数，接收数字x和p作为参数，获取x左侧和右侧各p个质数，返回所有这些元素的平均值。我已经写出了代码，但希望能降低它的时间复杂度。

我的代码如下：

#include <stdio.h>

int is_prime(int n)
{
    if (n == 1)
        return 0;
    
    if (n == 2 || n == 3)
        return 1;
    
    if (n % 2 == 0 || n % 3 == 0)
        return 0;
    
    for (int i = 5; i * i <= n; i = i + 6)
    {
        if (n % i == 0 || n % (i + 2) == 0)
            return 0;
    }
    
    return 1;
}

double sum_of_primes(int x, int p)
{
    int sum = 0;
    int countls = 0;
    int countrs = 0;
    int count = 0;

    if (is_prime(x))
    {
        sum = x;
        count = 1;
    }

    int i = x - 1;
    int j = x + 1;
    while (countls < p)
    {
        if (is_prime(i))
        {
            sum += i;
            countls++;
            count++;
        }   
        i--;
    }

    while (countrs < p)
    {  
        if (is_prime(j))
        {
            sum += j;
            countrs++;
            count++;
        }     
        j++;
    }
    return (double)sum / count;
}

int main()
{         
   int x, p;
   scanf("%d %d", &x, &p);

   printf("%f", sum_of_primes(x, p));
   return 0;
}

核心优化思路：预生成质数表 #

你的代码中每次判断质数都调用is_prime，当x很大或者p较大时，重复检查大量数字会导致时间累积。改用**埃拉托斯特尼筛法（埃氏筛）**预先生成足够范围的质数标记数组，可以一次性完成所有质数判断，避免重复计算。

优化后的代码示例

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

// 估算右侧需要的最大范围，留足够余量
int estimate_max(int x, int p) {
    if (x <= 2) return p * 10; // 处理x极小的情况
    double ln_x = log(x + p);
    return x + (int)(p * (ln_x + 2)); // 基于质数定理估算范围
}

// 埃氏筛生成质数标记数组
void sieve(int max_size, char* is_prime) {
    // 初始化所有数为质数（0和1除外）
    for (int i = 0; i <= max_size; i++) {
        is_prime[i] = 1;
    }
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i * i <= max_size; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= max_size; j += i) {
                is_prime[j] = 0;
            }
        }
    }
}

double sum_of_primes(int x, int p) {
    int sum = 0;
    int countls = 0;
    int countrs = 0;
    int count = 0;

    // 估算初始需要的最大范围
    int max_num = estimate_max(x, p);
    char* is_prime = (char*)malloc((max_num + 1) * sizeof(char));
    if (!is_prime) {
        printf("内存分配失败\n");
        return 0.0;
    }
    sieve(max_num, is_prime);

    // 检查x本身是否为质数
    if (x <= max_num && is_prime[x]) {
        sum = x;
        count = 1;
    }

    // 找左侧p个质数
    int i = x - 1;
    while (countls < p && i >= 2) {
        if (is_prime[i]) {
            sum += i;
            countls++;
            count++;
        }
        i--;
    }

    // 找右侧p个质数，初始范围不够时动态扩展
    int j = x + 1;
    while (countrs < p) {
        if (j > max_num) {
            // 扩展筛的范围
            max_num += p * 5;
            is_prime = (char*)realloc(is_prime, (max_num + 1) * sizeof(char));
            if (!is_prime) {
                printf("内存分配失败\n");
                return 0.0;
            }
            sieve(max_num, is_prime);
        }
        if (is_prime[j]) {
            sum += j;
            countrs++;
            count++;
        }
        j++;
    }

    double avg = (double)sum / count;
    free(is_prime);
    return avg;
}

int main() {
    int x, p;
    scanf("%d %d", &x, &p);
    printf("%f", sum_of_primes(x, p));
    return 0;
}

额外优化细节 #

1. 范围估算：基于质数定理估算右侧需要的最大范围，避免一开始就分配过大的内存；如果初始范围不够，动态扩展并重新筛法。
2. 筛法效率：埃氏筛的时间复杂度是O(n log log n)，相比逐个判断质数的O(sqrt(n))单次调用，在批量查找时效率提升明显。
3. 内存管理：使用malloc和realloc动态分配内存，避免固定大小数组的局限性，使用完后及时释放内存。

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