C语言求n以内最大的k个素数

在C语言中，求n以内最大的k个素数可以通过几种算法实现，比如埃拉托斯特尼筛法（Sieve of Eratosthenes）结合优先队列（例如`priority_queue`）。以下是简单的步骤：

1. **初始化**：创建一个布尔数组`isPrime[n+1]`，所有元素初始值设为true。表示从0到n之间的所有数字都是素数。

2. **筛选素数**：从2开始，将`isPrime[2]`设为false，并通过埃拉托斯特尼筛法去除所有其倍数的非素数。遍历到√n，每次遇到素数就更新后续的倍数。

3. **优先队列操作**：用`priority_queue<int>`存储前k个素数，初始大小为k。从大到小维护这个队列。当找到一个新的素数`num`且队列已满（即大小等于k），则弹出最小的素数并替换为`num`；否则直接添加到队列。

4. **结果输出**：当`num`大于n时，跳出循环。最后，队列中的k个元素就是n以内的最大素数。

下面是伪代码形式的示例：

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

bool isPrime(int num) {
    if (num <= 1)
        return false;
    for (int i = 2; i * i <= num; ++i)
        if (num % i == 0)
            return false;
    return true;
}

void sieveOfEratosthenes(int n, int k, std::priority_queue<int>& primeQueue) {
    bool* isPrime = new bool[n+1];
    for (int i = 2; i <= n; ++i)
        isPrime[i] = true;

    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i)
                isPrime[j] = false;
        }
    }

    int count = 0;
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i])
            primeQueue.push(i);
        else if (count < k && primeQueue.top() > i) {
            primeQueue.pop();
            primeQueue.push(i);
            count++;
        }
    }
    delete[] isPrime;
}

int main() {
    int n = 100, k = 5; // 求100以内的最大5个素数
    std::priority_queue<int> primeQueue(k); // 初始化一个能存放k个整数的队列
    sieveOfEratosthenes(n, k, primeQueue);

    printf("The largest %d primes within %d are: ", k, n);
    while (!primeQueue.empty()) {
        printf("%d ", primeQueue.top());
        primeQueue.pop();
    }
    return 0;
}