- 题目描述：
Output the k-th prime number.
- 输入：
k≤10000
- 输出：
The k-th prime number.
- 样例输入：
3 7
- 样例输出：
5 17
这道题是求第k个素数，因为k最大为10000,用户每输入一次求一次第k个素数，感觉会有很多重复的计算，倒不如刚开始的时候就将前10000个素数都求出来，之后对于用户的输入就可以直接按下标输出了。这里的关键是如何对求素数这个函数进行时间的优化。其实求素数是一个比较老的问题了，在没有时间要求的情况下，我们可以很简单的进行2～N的判断，若其中有一个数能够整除给定的N的话，说明它不是素数。这是法一。进一步优化的话，发现只要N的偶数肯定不是素数，若N为奇数，只要从3～N判断，若其中一个数能够整除给定的N的话，说明它不是素数，这里的步长可以设置为2。再进一步优化，对于上一种方法，我们发现当N为奇数时，只要从3～根号N的判断就行了，同样步长设置为2至此，已经可以在1秒内出结果了。实际测得时间为20ms#include <iostream> #include <math.h> #include <cstring> using namespace std; int c[10010]; bool prime(int test){ if(test%2 == 0) return 0; for(int i=3;i<=sqrt(test);i=i+2){ if(test%i == 0) return 0; } return 1; } int main(){ int a; memset(c,0,sizeof(c)); int k = 1; for(int i=2;;i++){ if(i == 2){ c[k] = 2; k++; continue; } if(prime(i)){ c[k] = i; k++; } if(k>10000) break; } while(cin>>a){ cout<<c[a]<<endl; } }
版权声明：本文为Jaster_wisdom原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。