呓语 | 杨英明的个人博客

专注于c++、Python,欢迎交流

By

蓝桥杯 算法训练 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

##原创声明 **转载请注明:[呓语](http://www.yangyingming.com) » [蓝桥杯 算法训练 Torry的困惑(基本型)(水题,筛法求素数)](http://www.yangyingming.com/article/95)**