【hdoj4548】美素数

谁践踏了优雅 2022-09-23 15:43 149阅读 0赞

![这里写图片描述][20160721082938979]  
![这里写图片描述][20160721082954636]  
本题最容易犯的错误是超时。这个方法可有效避免超时，31ms ac哦。  
应用素数打表，然后再次对美素数打表，用一个数组存储从0—1000000分别拥有的美素数和。  
随后要做的就是用这个负责存储的数组，在给定区间上做减法。

#include<stdio.h>
    #include<math.h>
    bool su[1000001],sum[1000001];
    int b[1000001];
    void nud() {
        int t,n;
        for(int l=2; l<1000001; l++) {
            if(!su[l])
                for(int j=l*2; j<1000001; j+=l)
                    su[j]=true;
        }
        su[0]=su[1]=true;
        for(int l=0; l<1000001; l++) {
            t=0;
            if(!su[l]) {
                n=l;
                while(n) {
                    t+=n%10;
                    n/=10;
                }
                if(!su[t])
                    sum[l]=true;
            }
        }
        n=0;
        for(int l=0; l<1000001; l++) {
            if(sum[l])
                n++;
            b[l]=n;
        }
    }
    int main() {
        int T,p=0,x,y;
        nud();
        scanf("%d",&T);
        while(T--) {
            scanf("%d %d",&x,&y);
            printf("Case #%d: %d\n",++p,b[y]-b[x-1]);
        }
        return 0;
    }

[hdoj4548][]

[20160721082938979]: /images/20220720/1d6939dfdfb14de498659d79a04c98a3.png
[20160721082954636]: /images/20220720/304726fe5c7b443b9e312085126c97c9.png
[hdoj4548]: http://acm.hdu.edu.cn/showproblem.php?pid=4548

发表评论取消回复

表情：

评论列表（有 0 条评论，149人围观）

还没有评论，来说两句吧...

相关阅读

相关【hdoj4548】美素数

![这里写图片描述][20160721082938979] ![这里写图片描述][20160721082954636] 本题最容易犯的错误是超时。这个方法可有效避免超时

谁践踏了优雅/ 2022年09月23日 15:43/ 0 赞/ 150 阅读

相关 hdoj 1016 Prime Ring Problem【素数环】

Prime Ring Problem Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/3276

痛定思痛。/ 2022年08月08日 15:58/ 0 赞/ 206 阅读

相关 hdoj1951

Bridging signals Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65536/32768

比眉伴天荒/ 2022年08月04日 08:37/ 0 赞/ 145 阅读

相关 HDOJ 1431-素数回文【删除大量无关数据】

素数回文 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

￡神魔★判官ぃ/ 2022年07月26日 00:07/ 0 赞/ 235 阅读

相关 HDOJ2037

题目：[http://acm.hdu.edu.cn/showproblem.php?pid=2037][http_acm.hdu.edu.cn_showproblem.php_

浅浅的花香味﹌/ 2022年06月08日 00:41/ 0 赞/ 174 阅读

相关 hdoj1213

一道简单的并查集题目hdoj1212 include<iostream> using namespace std; int T,N,M; in

Bertha 。/ 2022年06月07日 00:21/ 0 赞/ 161 阅读

相关 G - 美素数

G - 美素数 HPU专题训练（-1）GCD&&素筛&&快速幂\_\_\_\_\_G - 美素数　　小明对数的研究比较热爱，一谈到数，脑子里就涌现出好多数的问题，

Bertha 。/ 2022年06月01日 07:55/ 0 赞/ 214 阅读

相关 HDOJ 1008

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] Elevator Time Limit: 200

野性酷女/ 2022年01月15日 01:37/ 0 赞/ 288 阅读

相关 HDU4548 美素数

问题链接：[HDU4548 美素数][HDU4548]。基础练习题，用C语言编写程序。问题简述：参见上述链接。问题分析：美素数定义为一个数是素数并且其各位数

淩亂°似流年/ 2021年12月21日 05:34/ 0 赞/ 258 阅读

相关 HDU - 4548 - 美素数【数论 + 打表】题解

目录 1.题目 2.代码 1.题目小明对数的研究比较热爱，一谈到数，脑子里就涌现出好多数的问题，今天，小明

柔光的暖阳◎/ 2021年07月25日 02:22/ 0 赞/ 426 阅读