优化求解---第n小的质数

注意事项:优化求解过程。

优化1：第二层for循环中的sqrt(i),因数都是成对出现的。比如，100的因数有：1和100，2和50，4和25，5和20，10和10。看出来没有？成对的因数，其中一个必然小于等于100的开平方，另一个大于等于100的开平方。

优化2：sum相当于计数器，在第二层for循环中，如果sum的的数大于2，那个数绝对不是质数，直接退出其他的不用再除了

样例输入

10000

样例输出

104729

参考代码:

#include<stdio.h>

#include<math.h>

int main() {

int n, a[20000]={0},b[20000]={0},s = 1;

scanf("%d", &n);

//104800只是为了计算题目中要求的最大范围的结果，其他的可以自己试试。注意太大的静态数组无法保存，需要动态扩容才行

for (int i = 2; i <= 104800; i++) {

      int sum = 0;//置局部变量sum为计数器，每计算一个数完后就恢复为1

     for (int j = 1; j <= sqrt(i); j++) {

          if (i % j == 0)

          sum++;

          if (sum > 2)

          break;

}

//用sum来判断什么时候保存进数组

if (sum < 2) {

         a[s] = i;//保存进数组a中

         s++;//s为记录下标

    }

}

//将a数组中的元素重新排序，按序查找输出即可

for(int i = 1;i <= n;i++){

     b[i] = a[i];

}

printf("%d", b[n]);

return 0;

}