hdu 4548 筛法求素数 打表

时间:2022-03-23 06:18:48

题目:http://acm.hdu.edu.cn/showproblem.php?pid=4548

Problem Description
  小明对数的研究比较热爱,一谈到数,脑子里就涌现出好多数的问题,今天,小明想考考你对素数的认识。
  问题是这样的:一个十进制数,如果是素数,而且它的各位数字和也是素数,则称之为“美素数”,如29,本身是素数,而且2+9 = 11也是素数,所以它是美素数。
  给定一个区间,你能计算出这个区间内有多少个美素数吗?
 
Input
第一行输入一个正整数T,表示总共有T组数据(T <= 10000)。
接下来共T行,每行输入两个整数L,R(1<= L <= R <= 1000000),表示区间的左值和右值。
 
Output
对于每组数据,先输出Case数,然后输出区间内美素数的个数(包括端点值L,R)。
每组数据占一行,具体输出格式参见样例。
 
Sample Input
3
1 100
2 2
3 19
 
Sample Output
Case #1: 14
Case #2: 1
Case #3: 4

筛法求素数:要求至少在2分钟内盲敲出筛法来(打表)

以下是对于1百万以内的筛法

 for(int i=;i<;i++){
if(!p[i]){
for(int j=i*i;j<N;j+=i){
p[j] = ;
}
}
}

PS:一般的来说,需要使用到素数表时,都采用打表的方式,不然肯定会TLE的

 #include<iostream>
#include<string.h>
#include<stdio.h> using namespace std; #define N 1000005 bool p[N];
bool k[N];
int num[N]; void prime(){
for(int i=;i<;i++){
if(!p[i]){
for(int j=i*i;j<N;j+=i){
p[j] = ;
}
}
}
for(int i=;i<N;i++){
if(!p[i]){
int n=i;
int sum =;
while(n>){
sum+=(n%);
n/=;
}
if(!p[sum])
k[i] = ;
}
if(k[i])
num[i] = num[i-]+;
else
num[i] = num[i-];
}
return ;
} int main(){
int n,l,r,i,ca,cout;
memset(p,,sizeof(p));
memset(k,,sizeof(k));
memset(num,,sizeof(num));
num[]=,num[]=,num[]=;
p[]=,p[]=,p[]=;
k[]=,k[]=,k[]=;
prime();
ca = ;
cin>>n;
while(n--){
cin>>l>>r;
printf("Case #%d: %d\n",ca++,num[r]-num[l-]);
}
return ;
}

hdu 4548 筛法求素数 打表的更多相关文章

  1. 埃氏筛法求素数&amp&semi;构造素数表求素数

    埃氏筛法求素数和构造素数表求素数是一个道理. 首先,列出从2开始的所有自然数,构造一个序列: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 1 ...

  2. Algorithm --&gt&semi; 筛法求素数

    一般的线性筛法 genPrime和genPrime2是筛法求素数的两种实现,一个思路,表示方法不同而已. #include<iostream> #include<math.h> ...

  3. 蓝桥杯 算法训练 Torry的困惑&lpar;基本型&rpar;(水题,筛法求素数)

    算法训练 Torry的困惑(基本型) 时间限制:1.0s   内存限制:512.0MB      问题描述 Torry从小喜爱数学.一天,老师告诉他,像2.3.5.7……这样的数叫做质数.Torry突 ...

  4. UVA 10006 - Carmichael Numbers 数论(快速幂取模 &plus; 筛法求素数)

      Carmichael Numbers  An important topic nowadays in computer science is cryptography. Some people e ...

  5. 筛法求素数Java

    输出:一个集合S,表示1~n以内所有的素数 import java.util.Scanner; public class 筛法求素数 { public static void main(String[ ...

  6. JD 题目1040:Prime Number (筛法求素数)

    OJ题目:click here~~ 题目分析:输出第k个素数 贴这么简单的题目,目的不清纯 用筛法求素数的基本思想是:把从1開始的.某一范围内的正整数从小到大顺序排列, 1不是素数,首先把它筛掉.剩下 ...

  7. 2018牛客网暑期ACM多校训练营(第三场) H - Diff-prime Pairs - &lbrack;欧拉筛法求素数&rsqb;

    题目链接:https://www.nowcoder.com/acm/contest/141/H 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 262144K,其他语言524288K ...

  8. &lt&semi;转载&gt&semi;一般筛法和快速线性筛法求素数

    素数总是一个比较常涉及到的内容,掌握求素数的方法是一项基本功. 基本原则就是题目如果只需要判断少量数字是否为素数,直接枚举因子2 ..N^(0.5) ,看看能否整除N. 如果需要判断的次数较多,则先用 ...

  9. POJ2739&lowbar;Sum of Consecutive Prime Numbers【筛法求素数】【枚举】

    Sum of Consecutive Prime Numbers Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 19350 Ac ...

随机推荐

  1. &lbrack;No0000A9&rsqb;实用word用法

    目录  TOC \o "1-3" \h \z \u 三招去掉页眉那条横线.... PAGEREF _Toc465252982 \h 08D0C9EA79F9BACE118C8200 ...

  2. CentOS7&period;0关于libguestfs的bug

    libguestfs,libguestfs-tools是用来在不启动虚拟机的情况下,快速简单访问虚拟机磁盘的工具. 今天在CentOS7.0系统上通过guestmount命令去mount虚拟机磁盘的时 ...

  3. Spring配置,JDBC数据源及事务

    <?xml version="1.0" encoding="UTF-8"?> <beans xmlns="http://www.sp ...

  4. Android应用程序开发之图片操作(一)——Bitmap,surfaceview,imageview,Canvas

    Android应用程序开发之图片操作(一)——Bitmap,surfaceview,imageview,Canvas   1,Bitmap对象的获取 首先说一下Bitmap,Bitmap是Androi ...

  5. poj 1125 谣言传播 Floyd 模板题

    假如有3个点 点1到点2要5分钟 点1到点3要3分钟 那么5分钟的时间可以传遍全图 所以要先找一个点到其他点的最长时间 再从最长的时间里找出最小值 Sample Input 3 // 结点数2 2 4 ...

  6. JavaScript substr&lpar;&rpar; 字符串截取函数使用详解

    substr 定义和用法 substr() 方法可在字符串中抽取从 start 下标开始的指定数目的字符. 语法 stringObject.substr(start,length) 如果 length ...

  7. 2018年12月7日 字符串格式化2 format与函数1

    tp7="i am \033[44;1m %(name)-25.6s\033[0m"%{"name":"sxj2343333"} print ...

  8. WordPress基础:wp&lowbar;list&lowbar;pages显示页面信息列表

    函数:wp_list_pages($args) 作用:列出某个分类下的分类项目 常见参数说明: 参数 用途  值   sort_column  排序方式 post_title 按标题排序 [默认] m ...

  9. 实验1 熟悉Linux开发环境 实验报告

    参见http://www.cnblogs.com/lhc-java/p/4970269.html

  10. POI的XWPFParagraph&period;getRuns分段问题 多余逗号

    POI的XWPFParagraph.getRuns分段问题 2018年08月28日 09:49:32 银爪地海贼 阅读数:376   这是我的模板 后台打印出来是分段的 造成这样的原因是${name} ...