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 条评论
登录 后参与评论

相关文章

来自专栏极客慕白的成长之路

ACM札记二

由数学基本定理可知:任何一个大于1的非素数整数(即合数)都可以唯一分解成若干个素数的乘积。编写程序,从控制台读入一个合数(合数的大小不会超过int数据类型表示的...

691
来自专栏chenjx85的技术专栏

leetcode-204-Count Primes

2588
来自专栏ml

java学习之协调同步的线程

            当一个线程使用的同步方法中用到某个变量,而此变量有需要其他线程修改后才能符合本线程的需要,      那么可以在同步方法中使用wait(...

3379
来自专栏Hongten

java多线程系列_使用Runnable接口创建线程(3)

实现Runnable接口的类必须使用Thread类的实例才能创建线程。通过Runnable接口创建线程分为两步:

883
来自专栏数据结构与算法

1462 素数和

1462 素数和 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 青铜 Bronze 题目描述 Description 给定2个整...

2817
来自专栏河湾欢儿的专栏

数组

911
来自专栏五分钟学算法

每天一算:Reverse String

我们会在每天早上8点30分准时推送一条LeetCode上的算法题目,并给出改题目的动画解析以及参考答案,每篇文章阅读时长为五分钟左右。

912
来自专栏程序生活

求一个数n次方后的末尾数(数论/快速幂)问题描述解题思路代码实现运行结果参考

问题描述 hdu1061-Rightmost Digit hdu1097-A hard puzzle 这两个oj题目思路几乎一样,都是为了快速求出一个数n次...

4727
来自专栏swag code

swap()交换两个变量的方法汇总

1054
来自专栏木子昭的博客

寻找"单身数"

一个有N个数的数组里, 每个数字都出现两次, 现在取出一个数, 根据剩下的数字, 猜测取出的数的值(要求时间复杂度为N, 空间复杂度为1) 异或运算 两个相同...

2675

扫码关注云+社区

领取腾讯云代金券