九度OJ-1040：Prime Number

做这道题时候毛病出在很坑爹的地方：由于需要预处理的数据太大，导致以下代码出了问题：

for (int i=2;i<110000;i++){ if (isPrime[i]==true){ prime[primeSize]=i; primeSize++; for (int j=2;i*j<110000;j++){//*********// isPrime[i*j]=false; } } }　　标记处若写成 for (int j=i;i*j<110000;j++){

则会出现当i跑到46000+时i*j=i*i这个数出现溢出。故此处无法让j从i开始跑，只能老老实实从2开始跑了。

题目地址：点击打开链接

题目描述：

Output the k-th prime number.

输入：

k≤10000

输出：

The k-th prime number.

样例输入： 3 7 样例输出： 5 17 来源： 2008年上海交通大学计算机研究生机试真题 答疑： 解题遇到问题?分享解题心得?讨论本题请访问： http://t.jobdu.com/thread-7764-1-1.html #include <iostream> using namespace std; int main(){ int k,primeSize; int prime[10500]; bool isPrime[110000]; //preprocess primeSize=0; for (int i=2;i<110000;i++){ isPrime[i]=true; } for (int i=2;i<110000;i++){ if (isPrime[i]==true){ prime[primeSize]=i; primeSize++; for (int j=2;i*j<110000;j++){ isPrime[i*j]=false; } } } //output while (cin>>k){ cout<<prime[k-1]<<endl; } return true; }