C语言程序设计教程（第三版）课后习题7.1 （C++描述 时间复杂度与空间复杂度较低）

解题思路:

双重循环+判断：

第一重循环出需要判断的数;

在判断排除去除二以外的所有偶数；//或者除去所有偶数，后面再添上2则可

第二重循环判断所有奇数中的素数

注意事项:

以节省时间复杂度与空间复杂度;

这用先定义了循环变量和存sqrt()结果的m;




参考代码:

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

int n,i,j=2;

float m;  //存sqrt(n)

cin>>n;

cout<<2<<endl;

for(i=3;i<n;i++) //第一重循环

{

m = sqrt(i);

if (i%j != 0) //筛选出所有奇数

{

for (j=3;j<=m;j+=2) //第二重循环

{

if(i%j == 0)

{

j = 2;

break;

}

}

if(j>m)

{

cout<< i <<endl;

}

j = 2;

}

}

return 0;

}