题目说明：求出前n个质数的乘积，并取模50000，其中n的范围是n<=100000
题目分析：这是一道求素数(质数)的题目。素数，是除了1和它自身外，不能被其他数整数的数。其中，2 是素数。
基本方法可以是，对每个数，判断它是不是素数，很容易求解。这里for循环内遍历到根号n,就可以了，节约一半时间。
代码实现1：
//普通解法：sqrt(n) #include <iostream> using namespace std; bool prime(int num){ if(num==2) return true; for(int i=2;i*i<=num;i++){ if(num%i==0){ return false; } } return true; } int main(){ int n; cin>>n; int result = 1; int count = 1; for(int i=2;count<=n;i++){ if(prime(i)){ result = (result * i)P000; count++; } } cout<<result<<endl; return 0; }比较快捷的办法是：利用原理“无论一个数是素数，还是合数，它的倍数肯定不是素数”。合数的倍数不用考虑，因为合数肯定是某个素数的倍数，所以只需考虑素数的倍数。这样的话，我们可以排除掉很多数，便于后期的判断。具体来说，就是用一个数组check,先假设check[n]={0}，所有数都为素数(假定i是素数的话，check[i]=0)。后面只要出现不是素数的数，则将其check[i]置为1.此外，这种方法还需要知道到第100000个质数会是多大，这样我才能设置check数组的大小，这里我是设置一个较大值4000000,根据问题需要可以修改。
代码实现2：
//普通筛选法 #include <iostream> #include <string.h> using namespace std; int main(){ int n; cin>>n; int prime[100001]; //用来存储素数的数组2，3，5，7，9…… bool check[4000000]; memset(check,0,sizeof(check)); //先假定所有数都为素数 int j = 0; for(int i=2;i<4000000;i++){ if(!check[i]){ prime[j++] = i; //则i是素数 for(int k=2*i;k<4000000;k=k+i) check[k] = 1; //素数的倍数都不是素数 } if(j==n) //素数数组里有n个数，则退出循环 break; } long long result = 1; for(int i=0;i<n;i++){ result = (result * prime[i])P000; } cout<<result<<endl; }还有一种比较高级的筛选法是欧拉筛选法，可以保证所有的合数只被筛选过一次，不会被重复标记。在O(n)的时间实现。
具体方法：当i在2到n之间循环时，prime[]数组保留着当前已知的素数，对于某一次的循环i=value, 如果它没有标记过，就是素数。然后遍历素数数组prime,将每个素数都乘以value倍，将其标记为非素数。其中，当value能被某个素数整除时，就跳出循环，后面就不考虑了。通过这样的手段，来避免重复剔除非素数。
结合例子分析：当i=2，prime[0]=2, check[2*2] = check[4] = 1;
当i=3, prime[0]=2, prime[1]=3, check[3*2] = check[6] = 1, check[3*3] = check[9] = 1;
当i=4，prime[0]=2, prime[1]=3, check[4*2] = check[8] = 1, check[4*3] = check[12] = 1; 这里一定要注意，红色部分不需要计算，为什么？ 因为计算check[4*2] = check[8] = 1时，我们注意到4能被2整除了，即4%2==0,所以后面的就不考虑了。为什么可以不考虑？因为我发现当i=4是，i是2的倍数，所以下一个4*3一定可以写成2*2*3，即当i=6时会被计算，2*6。
理论：后面的大合数，可以用更小的质数去剔除，比如，12=6*2可以用素数2来剔除，而不用4*3来剔除。为什么要这样剔除？答案是可以保证唯一性，即每个非素数只被剔除了一次。Why？ 因为每个非素数可以唯一地用最小的质数和另一个数的乘积表示。
结果是真的快了很多...
代码实现：
//欧拉筛选法 #include <iostream> #include <string.h> using namespace std; int main(){ int n; cin>>n; int prime[100001]; //用来存储素数的数组2，3，5，7，9…… bool check[4000000]; memset(check,0,sizeof(check)); //先假定所有数都为素数 int tot = 0; for(int i=2;i<4000000;i++){ if(!check[i]){ prime[tot++] = i; //则i是素数 } for(int j=0;j<tot&&i*prime[j]<4000000;j++){ check[i*prime[j]] = 1; if(i%prime[j]==0) //i是prime[j]的倍数 break; } if(tot==n) //素数数组里有n个数，则退出循环 break; } long long result = 1; for(int i=0;i<n;i++){ result = (result * prime[i])P000; } cout<<result<<endl; }此外，本题的测试数据，就一个n=8,所以测评非常水....
