任务详情
-
在openEuler(推荐)或Ubuntu或Windows(不推荐)中完成下面任务，使用git管理过程，至少提交三次
-
参考《密码工程》p107伪代码基于Eratosthenes算法实现 int SmallPrimeList(int n, int *plist, int *len), 其中plist返回素数列表，len返回列表长度（5’）
-
写出测试代码，至少包括 n=2, n=你的四位学号，n>2^20次方的测试代码,提交代码和运行结果截图，git log截图（10)
-
提交使用Markdown并转为PDF，或者使用doc，docx格式
任务内容
1、测试代码
点击查看代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 标记函数，用于标记合数
void markComposites(int *isPrime, int n) {
for (int p = 2; p * p <= n; ++p) {
if (isPrime[p]) {
for (int i = p * p; i <= n; i += p) {
isPrime[i] = 0; // 标记为合数
}
}
}
}
// 生成小于等于n的所有素数列表
int SmallPrimeList(int n, int *plist, int *len) {
// 如果n小于2，没有素数
if (n < 2) {
*len = 0;
return 0;
}
// 分配内存来标记是否为素数
int *isPrime = (int *)calloc(n + 1, sizeof(int));
if (isPrime == NULL) {
return -1; // 分配内存失败
}
// 初始化所有数字为素数（除了0和1）
for (int i = 2; i <= n; ++i) {
isPrime[i] = 1;
}
// 标记合数
markComposites(isPrime, n);
// 填充plist并计算素数数量
int count = 0;
for (int i = 2; i <= n; ++i) {
if (isPrime[i]) {
plist[count++] = i;
}
}
// 释放内存
free(isPrime);
// 设置返回的长度
*len = count;
return 0; // 成功
}
int main() {
int n;
printf("Enter a positive integer n (not greater than 2^20): ");
scanf("%d", &n); // 从用户处获取输入
// 检查输入是否为正整数且不超过2的20次方
const int MAX_N = 1 << 20; // 2的20次方
if (n <= 0 || n > MAX_N) {
printf("n must be a positive integer less than or equal to 2^20.\n");
return 1; // 输入错误，退出程序
}
// 根据n的大小动态分配plist的内存
int *plist = (int *)malloc(MAX_N * sizeof(int)); // 分配足够的空间来容纳最多MAX_N个素数
if (plist == NULL) {
printf("Memory allocation failed.\n");
return 1; // 内存分配失败，退出程序
}
int len = 0;
// 生成素数列表
int result = SmallPrimeList(n, plist, &len);
if (result == 0) {
printf("Prime numbers less than or equal to %d are:\n", n);
for (int i = 0; i < len; ++i) {
printf("%d ", plist[i]);
}
printf("\n");
} else {
printf("Error occurred during prime number generation.\n");
}
// 释放plist内存
free(plist);
return 0;
}
