专栏首页数据结构与算法177. [USACO Jan07] 有限制的素数

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

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'.

思路:先用筛法求素数,然后再遍历所有区间内的数,取出来,依次取出每一位上的数,做判断。如果与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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ4773: 负环(倍增Floyd)

    一个很显然的思路(然而我想不到是用\(f[k][i][j]\)表示从\(i\)号点出发,走\(k\)步到\(j\)的最小值

    attack
  • 洛谷P4716 【模板】最小树形图(朱刘算法)

    attack
  • 1058 合唱队形 2004年NOIP全国联赛提高组

    1058 合唱队形 2004年NOIP全国联赛提高组  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结...

    attack
  • 联系人字母导航集大成者

    联系人字母导航条已经出来很多年都交互了,其UI组合无非是悬浮字母列表+侧边栏都字母选择(PinnedHeadList+siderBar)。这里炒...

    jerrypxiao
  • [USACO06JAN]牛的舞会 Tarjan模版

    用户2965768
  • Codeforces Round #559

    接下来n个数a1~an是男生送出的最小数量,然后是m个 b1~bm 是女生收到的最大数量。

    用户2965768
  • View的工作原理

    View的绘制流程是从ViewRoot的PerformTraversals方法开始的。它经过measure,layout,draw三个过程将view绘制出来。m...

    提莫队长
  • 对顶堆求区间k小(大)数

    首先,这道题让我们求每次的第i大值,而i是会移动的——那我们就可以理解为,我们需要知道第i大值和第i+1大值(请撕烤)。那用什么数据结构呢?

    glm233
  • CodeForces #549 Div.2 C Queen

    ShenduCC
  • 浙大版《C语言程序设计(第3版)》题目集 习题6-5 使用函数验证哥德巴赫猜想

    本题要求实现一个判断素数的简单函数,并利用该函数验证哥德巴赫猜想:任何一个不小于6的偶数均可表示为两个奇素数之和。素数就是只能被1和自身整除的正整数。注意:1不...

    C you again 的博客

扫码关注云+社区

领取腾讯云代金券