★ 输入文件: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'.
思路:先用筛法求素数,然后再遍历所有区间内的数,取出来,依次取出每一位上的数,做判断。如果与d相同,tot++;
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 using namespace std;
5 int a,b,n;
6 int flag=0;
7 int tot=0;
8 int vis[10000001];
9 int main()
10 {
11 freopen("qprime.in","r",stdin);
12 freopen("qprime.out","w",stdout);
13 cin>>a>>b>>n;
14 for(int i=2;i<=sqrt(b+0.5);i++)
15 {
16 if(!vis[i])
17 for(int j=i*i;j<=b;j=j+i)
18 {
19 vis[j]=1;
20 }
21 }
22 for(int i=a;i<=b;i++)
23 {
24 if(vis[i]==0)
25 {
26 flag=0;
27 int d=i;
28
29 while(d!=0)
30 {
31 int gw=d%10;
32 if(gw==n)
33 {
34 flag=1;
35 break;
36 }
37 else
38 {
39 d=d/10;
40 }
41 }
42 if(flag==1)
43 tot++;
44 }
45 else continue;
46
47 }
48 cout<<tot;
49 fclose(stdin);
50 fclose(stdout);
51 return 0;
52 }