首页 > 代码库 > 蓝桥杯 算法训练 Torry的困惑(基本型)（水题，筛法求素数）
蓝桥杯 算法训练 Torry的困惑(基本型)（水题，筛法求素数）
算法训练 Torry的困惑(基本型)
时间限制：1.0s 内存限制：512.0MB
问题描述
Torry从小喜爱数学。一天，老师告诉他，像2、3、5、7……这样的数叫做质数。Torry突然想到一个问题，前10、100、1000、10000……个质数的乘积是多少呢？他把这个问题告诉老师。老师愣住了，一时回答不出来。于是Torry求助于会编程的你，请你算出前n个质数的乘积。不过，考虑到你才接触编程不久，Torry只要你算出这个数模上50000的值。
输入格式
仅包含一个正整数n，其中n<=100000。
输出格式
输出一行，即前n个质数的乘积模50000的值。
样例输入
1
样例输出
2
水题，筛法求素数。
思路：筛法求素数。用一个数组标记是否为素数，循环的时候首先查看该数的标记，如果不是素数，则可以直接跳过。另外不管一个数是不是素数，他的倍数一定不是素数。写一个循环，依次标记。
不知道不用筛法，会不会通过。
代码：
1 #include <iostream>
2
3 using namespace std;
4 bool prime(int n) //判断是否为素数
5 {
6 int i;
7 for(i=2;i<n;i++)
8 if(n%2==0)
9 break;
10 if(i<n)
11 return false;
12 else
13 return true;
14 }
15 int main()
16 {
17 int i,j,n,sum,ans;
18 bool p[100001]={0};
19 while(cin>>n){
20 ans = 1;
21 sum = 0;
22 i = 2;
23 while(sum<n){
24 if(!p[i] && prime(i)){ //判断该数i是否为素数
25 ans = ans*i%50000;
26 sum++;
27 for(j=i+i;j<=100000;j+=i) //筛法求素数
28 p[j]=true;
29 }
30 i++;
31 }
32 cout<<ans<<endl;
33 }
34 return 0;
35 }
Freecode : www.cnblogs.com/yym2013
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。