编写一个完整c语言程序,运用埃拉托色尼筛法给定 n 和 k,找出第 k 个被删除的整数。 输入格式: 输入的第一行给出两个整数n,k。 2≤k<n≤1000 输出格式: 输出一个整数——表示第 k 个被划掉的整数。
时间: 2023-12-03 16:44:11 浏览: 77
c++,求被整除的数
以下是一个完整的C语言程序,实现了埃拉托色尼筛法找出第k个被删除的整数:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_N 1000
int primes[MAX_N]; // 存储筛出的素数
bool is_prime[MAX_N + 1]; // 标记每个数是否为素数
void sieve(int n) {
int i, j, cnt = 0;
for (i = 2; i <= n; i++) {
if (is_prime[i]) {
primes[cnt++] = i;
for (j = i * i; j <= n; j += i) {
is_prime[j] = false;
}
}
}
}
int main() {
int n, k, i, j, cnt = 0;
scanf("%d%d", &n, &k);
// 初始化,先假设所有数都是素数
for (i = 2; i <= n; i++) {
is_prime[i] = true;
}
sieve(n); // 筛出素数
// 遍历删除k个数
for (i = 0; i < cnt && cnt < k; i++) {
for (j = primes[i]; j <= n; j += primes[i]) {
if (is_prime[j]) {
is_prime[j] = false;
cnt++;
if (cnt == k) {
printf("%d\n", j);
return 0;
}
}
}
}
return 0;
}
```
程序中,首先定义了两个数组,`primes`用于存储筛出的素数,`is_prime`用于标记每个数是否为素数。然后使用埃拉托色尼筛法筛出`n`以内的素数,并将其存储到`primes`数组中。接着使用双重循环遍历每个素数的倍数,将其标记为非素数,并统计被删除的数的个数,直到删除了第`k`个数为止。最后输出第`k`个被划掉的整数。
阅读全文