请编程求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