数据结构实验报告：素数判断的算法设计分析与对比

1、实验目的

（1）通过程序设计体验算法的时间复杂度和空间复杂度；

（2）尝试优化算法，提高效率。

2、实验具体要求

（1）输出所有小于等于n（n为一个大于2的正整数，比如100）的素数；

（2）每行输出10个素数；

（3）尽可能采用较优算法。

3、实验设计思路

（1）思路一：让n被2~n-1 之间的每一个整数除，如果都不能被整除，那么n就是一个素数。

（2）思路二：让n被2~√n后之间的每一个整数除。如果n不能被2~√n间任一整数整除，n必定是素数。

4、实验源程序、程序调试结果

思路一：

#include

void main()

{ int n,i,j,z=0;

printf("请输入一个数：\n");

scanf("%d",&n);

for(i=2;i<=n;i++)

{

for(j=2;j

{

if(i%j==0)

break;

}

if(j==i)

{

printf("%5d",i);

z++;

if(z%10==0)

printf("\n");

}

}

}

思路二：

#include

#include

void main(){

int n;//输入的整数

int i;//循环次数

int k；//n的平方根

int z;//每行10个数

printf("输入一个整数："）;

scanf("%d",&n);

//求平方根，sqrt(）的参数为double类型，强制转换n的类型

k=(int)sqrt((double)n);

for(i=2;i<=k;i++){

for(j=2;j

if(n%i==0)

break;

} if(j==i){

printf(“%5d”,i);

z++;

if(z%10==0)

printf(“/n”);

}

}

return 0;

｝

 

5、程序调试过程中遇到的问题及解决办法

（1）缺失符号：思路一输入程序时漏打一个分号，报错后改正。

（2）void函数使用方法模糊：void表示不返回任何信息，不应该使用return语句。报错后删除return 0语句。

6、实验收获与体会

拿到题目第一反应还是学习c语言时期的老办法：挨个除。写完之后想到了学习的“降低时间或空间复杂度”，在网上查找另一种判断素数的方法之后又写了第二种思路，可以降低时间复杂度，虽然主观上效果不明显，但也让我亲自体验了一下算法设计。

另一方面，程序设计必须自己亲自动手进行实验，发现错误并想办法改正错误，才能掌握。另外要在掌握技术的同时细心检查，避免因为粗心产生的错误。