首页 > 代码库 > 177. 有限制的素数

177. 有限制的素数

177. [USACO Jan07] 有限制的素数

★   输入文件:qprime.in   输出文件:qprime.out   简单对比
时间限制:1 s   内存限制:128 MB

Farmer John 开始给奶牛们标记上素数的牌子,贝茜注意到了这一切,她对各种数的牌子很好奇。

请帮助贝茜算出从A到B (1 ≤ A ≤ B ≤ 4,000,000; B ≤ A + 1,000,000; B ≤ A + 2,000,000 ),其中包含数字D的素数的个数。

素数是只有两个两个约数(1 和 它本身)的正整数,例如 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

输入

第 1 行: 三个整数 A, B, and D

输出

第 1 行: 包含数字D的素数的个数。

样例输入

10 15 3

样例输出

1

输出解释

只有 13 包含 ‘3‘.

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 int a,b,d,s=0;
 6 bool pd(int x) ;
 7 bool pd2(int n,int m);
 8 int main()
 9 {
10     freopen("qprime.in","r",stdin);
11     freopen("qprime.out","w",stdout);
12     
13     scanf("%d%d%d",&a,&b,&d);    
14     for(int i=a;i<=b;++i)    
15     {
16         if(pd(i)&&pd2(i,d))s++;  //判断是否都符合;
17     }
18     printf("%d",s);  
19     fclose(stdin);
20     fclose(stdout);
21     return 0;    
22 }
23 bool pd(int x)      //判断素数
24 {
25     for(int i=2;i<=sqrt(x);++i)
26     if(x%i==0)return 0;
27     return 1;
28     
29 }
30 bool pd2(int n,int m) //判断是否包含d;
31 {
32     while(n!=0)    
33     {
34         if(n%10==m)return 1;    
35         n/=10;
36     }
37     return 0;
38 }

 

177. 有限制的素数