请编程求1000至1500之间的所有素数有几个?并把这些素数显示出来。
发布网友
发布时间：2024-10-24 03:43
共2个回答
热心网友
时间：2024-10-31 04:20
我不清楚你会用什么语言，我就写了一个C语言的程序，在C++平台上也能运行。
#include <stdio.h>
#include <stdlib.h>
//线性表
typedef struct Vector {
int* num;//一个数组
int length;//num数组的长度
};
//生成素数表,采用埃拉托色尼筛法
Vector* getPrimeTable(int length) {
int i, j;
int* table = (int*)malloc(sizeof(int) * length + 2);//素数表(下标表示数值,素组元素的内容表示下标是否为素数)
Vector* result = (Vector*)malloc(sizeof(Vector));//素数表(保存最终的结果)
for (i = 0; i <= length; i++)
table[i] = 1;//全部标记为素数
for (i = 2; i <= length; i++) {//整体遍历一遍数组
if (table[i] == 1) {//如果i是素数
for (j = 2; j * i <= length; j++) {//将所有i的倍数都取消素数标记
table[j * i] = 0;//撤销j的素数标记
}
}
}
result->num = (int*)malloc(sizeof(int) * length);//分配内存
result->length = 0;//赋初始值
for (i = 2; i <= length; i++) {//由于table是用数组元素的内容来表示下标对应的数是否为素数，因此需要转化为只保存素数的线性表
if (table[i] == 1) {
result->num[result->length++] = i;
}
}
return result;
}
Vector* getPrime(Vector* table,int begin,int end) {
Vector* res = (Vector*)malloc(sizeof(Vector));
res->num = (int*)malloc(sizeof(int) * (end-begin));
res->length = 0;
int i, j;
for (i = begin; i <= end; i++) {
for (j = 0; j < table->length; j++) {
if (i % table->num[j] == 0) {//若num中的数能够被table整除,说明该数不是素数
break;//不是素数,跳出循环
}
if (j == table->length - 1) {//如果j循环到了最后一次那么说明num中的数不能被任何table中的数字整除，因此该数一定是素数
res->num[res->length++] = i;//保存素数到结果集
}
}
}
return res;
}
int main() {
int tblLength = 40;//素数表的长度是40，因为40^2=1600>1500
Vector* tbl = getPrimeTable(tblLength);//素数表
Vector* res;//结果
int i;
res = getPrime(tbl, 1000,1500);//得到结果
printf("一共有%d个\n",res->length);//输出结果
for (int i = 0; i < res->length; i++) {
printf("%d\n", res->num[i]);
}
return 0;
}
运行结果截图
热心网友
时间：2024-10-31 04:15
1009到1499共71个。
