运用埃拉托色尼筛法求解一定范围内的素数.docx

目 录摘 要2求素数问题31数据结构设计32算法设计33函数流程图44调试测试运行45源程序5摘 要算法与数据结构在计算机科学与技术中，尤其是计算机软件设计中有着举足轻重的作用。其主要是讲述一个程序的逻辑结构和物理结构，及在已知结构上实现的算法，在设计程序时，我们应该首先考虑到我们要以怎样的逻辑结构来描述所要讨论的问题，且判断它的合理性，和可行性，为了能在计算机上实现问题的模拟实现，我们同时必须设计好在计算机上存储的物理结构，为了能够运行成功，必须要设计一套具有正确性，健壮性，可读性好的程序，来实现计算机上的模拟；其中算法，逻辑结构和物理结构相辅相成，任何一个环节出错都不能成功的完成问题在计算机上的模拟。程序如下：求解素数，运用埃拉托色尼筛法求解一定范围内的素数。埃拉托色尼筛法是建立一个2到N的表，在表中删除2的倍数，3的倍数，5的倍数，以此类推直到删除到，为止，表中都为素数。关键词： 素数 C语言 求素数问题埃拉托色尼筛法（Sieve of Eratosthenes）是一种用来求所有小于N的素数的方法。从建立一个整数2N的表着手，寻找i的整数，编程实现此算法，并讨论运算时间。1数据结构设计定义一个线性表链式存储结构，用来求所有小于N的素数typedef struct Node/定义链表int data;/存储数据struct Node *link;/定义指针指向下一个结点LinkList;2算法设计使用一个函数进行埃拉托色尼筛法，形参为建立的链表头节点和所求素数的范围最大值，没有返回值，函数对链表进行操作，从头节点开始读入数据删除其倍数，指针下移读入下一个数据，再删除其倍数，指针一直下移直到读入，停止下移，表中所有数据皆为素数。void eratosthenes(int max,LinkList *&head)/使用埃拉托色尼筛法筛选数字 LinkList *a,*b;a=head-link;for(;)if(a-datalink)if(b-link-data%a-data=0)b-link=b-link-link;b=b-link;a=a-link;else break;3函数流程图开始输入范围调用函数构建链表调用函数进行筛选数据调用函数输出链表结束图1-1 主程序运行图4调试测试运行1 提示输入素数的范围最大值时，输入300，打印出2-300内的所有素数，且统计素数个数为62.图1.2测试运行界面2 算法的时间复杂度O(N*lglgN)。5源程序#include#include#includetypedef struct Nodeint data;struct Node *link;LinkList;void buildList(int max,LinkList *&head)/构建链表函数 LinkList *l,*p;int i;head=(LinkList*)malloc(sizeof(LinkList);head-link=NULL;l=head;for(i=2;ilink=p;p-data=i;p-link=NULL;l=p;void eratosthenes(int max,LinkList *&head)/使用埃拉托色尼筛法 筛选数字 LinkList *a,*b;a=head-link;for(;)if(a-datalink)if(b-link-data%a-data=0)b-link=b-link-link;b=b-link;a=a-link;else break;void printList(LinkList *head)/输出链表 函数LinkList *q;int k=0;q=head-link;printf(范围内的素数有：);for(;)if(q=NULL)break;elseprintf( %d ,q-data);k+;q=q-link;printf(n 共有素数：%d 个,k);printf(n);int main()/主函数LinkList *head;int max;printf(使用埃拉托色尼筛法求素数n);printf(请输入要求素数的范围max=);scanf(%d,