HDOJ(HDU) 2138 How many prime numbers(素数-快速筛选没用上、)_谙忆的博客-程序员宝宝

技术标签: ❶ ACM  ----- HDOJ-JAVA  ACM之旅  ----- 素数相关  ❺ 算法及基础题  

Problem Description
Give you a lot of positive integers, just to find out how many prime numbers there are.

Input
There are a lot of cases. In each case, there is an integer N representing the number of integers to find. Each integer won’t exceed 32-bit signed integer, and each of them won’t be less than 2.

Output
For each case, print the number of prime numbers you have found out.

Sample Input
3
2 3 4

Sample Output
2

这个题目就是让你求一组的素数有多少个。
这个素数范围的数字有点大,所以不能用打表。
测试数据很水。。。直接判断就能过了。
不过判断的时候,有一个地方需要注意的,我在那个判断素数的方法注释了。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        //boolean db[] = new boolean[2147483647];
        //数组太大,不能打表!
        //dabiao(db);
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            long sum = 0;
            int m;
            for(int i=0;i<n;i++){
                m=sc.nextInt();
                if(prime(m)){
                    sum++;
                }
            }
            System.out.println(sum);
        }
    }

    //直接判断能过,说明数据比较水。
    private static boolean prime(int m) {
        for(int i=2;i<=Math.sqrt(m);i++){
         //***** 注意:i*i<=m  是会超时的,因为i*i每次都要计算
            if(m%i==0){
                return false;
            }
        }
        return true;
    }

    //素数筛选打表应该会超时
    private static void dabiao(boolean[] db) {
        Arrays.fill(db, true);
        for(int i=2;i<=Math.sqrt(db.length);i++){
            for(int j=i+i;j<db.length;j+=i){
                if(db[j]){
                    db[j]=!db[j];
                }
            }
        }
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_26525215/article/details/51319430

智能推荐

互联网日报 | 理想汽车登陆纳斯达克;苏宁易购会员数量突破6亿;高德地图上线“司机公厕”..._liudada8265的博客-程序员宝宝

今日看点✦理想汽车正式在纳斯达克挂牌上市,股价开盘大涨35%✦ 苏宁易购上半年实现营收1182.43亿元,会员数量突破6亿✦ 高德地图上线北京92处可临时停车公厕,车辆可临停15分钟✦...

SCI投稿前需要准备哪些材料?_EA-ISET学术的博客-程序员宝宝

今天EA-ISET协会给大家分享一篇关于SCI投稿知识的文章。好不容易写好文章,看准了一个杂志,撸起袖子准备投稿时,突然发现除了需要上传初稿附件外,必须上传一些其他附件,以及要求论文中必须在参考文献前附上一些利益等声明条款;比如:★常见附件材料:Cover Letter, Highlights, Reviewer suggestions,Checklist,Graphic Abstract等;★常见附在参考文献前的声明条款:Availability of data and material;

JDK、JRE、JVM和javac的关系_24只羊羊羊的博客-程序员宝宝_javac在jdk还是jre中

    .java为Java的源文件后缀,编写的代码需要写在.java文件中。    Javac编译器,用于读取Java源代码,并将其编译成字节代码。经过javac编译后形成.class,是字节码文件。    Java虚拟机(JVM)运行.class文件从而实现程序的运行。    1、JVM——java virtual machine,就是我们常说的java虚拟机,它是整个java实现...

Unsupervised Feature Learning via Non-Parametric Instance Discrimination_ML_NI_CSU的博客-程序员宝宝

论文地址:Unsupervised Feature Learning via Non-Parametric Instance Discriminationgithub代码:NCE代码摘要:在有标签数据上训练的神经网络分类器能够很好的捕捉图片间的视觉相似性。文章假设:我们能通过训练基于实例(将每一个样本视为单独的类别)的分类器代替基于类别的分类器,得到可以捕捉视觉相似性的特征表达。我们将其总结...

JavaScript忍者秘籍--学习笔记_waterwatermelon的博客-程序员宝宝

chapter 3 函数函数都一个name属性表示函数的名字。命名函数和匿名函数的区别?变量提升 声明(var)会被提升,初始化不会被提升。函数的作用域是指声明该函数的整个函数范围。arguments 参数–类数组this参数依赖函数调用的方式。调用上下文(invocation context)构造器的超能力1.创建一个新的空对象2.传递给构造器的对象是this参数(即刚刚创建的...

同桌的你之程序员版[摘]_weixin_33681778的博客-程序员宝宝

2019独角兽企业重金招聘Python工程师标准&gt;&gt;&gt; ...

随便推点

uboot-2015-07的start.S的文件启动过程_shenlong1356的博客-程序员宝宝

https://blog.csdn.net/u013904227/article/details/51648179https://www.cnblogs.com/debruyne/p/9208809.htmlhttps://blog.csdn.net/weixin_41734376/article/details/98586549

数据结构之通用树结构的实现_顾小豆的博客-程序员宝宝_树结构实现

之前我们讲了树的定义和操作,这节我们讲一下如何实现这些操作。既然要考虑如何实现,那就得说说树的存储结构。大家都知道树是非线性数据结构,显然我们无法用数组来表示树的逻辑结构。那我们应该怎么办呢?通过什么来表示呢?其实可以设计结构体数组对结点间的关系进行表述。如下图所示:从上图发现,将根结点的双亲定义为-1,表示其没有双亲;将根的孩子结点的双亲定义为0,表示其双亲是根结点;将根结点孩子1的孩子结点的双...

时间序列预测方法汇总:从理论到实践(附Kaggle经典比赛方案)_PaperWeekly的博客-程序员宝宝

作者 | Light学校 | 中国科学院大学研究方向 | 机器学习时间序列是我最喜欢研究的一种问题,这里我列一下时间序列最常用的方法,包括理论和实践两部分。理论部分大多是各路神仙原创的高...

windbg命令_ken_scott的博客-程序员宝宝

windbg命令linux下使用ulimit -S -c unlimited命令,可以使程序崩溃时生成core文件,使用gdb exec_file core_file就可以查看崩溃的程序,接着使用bt就基本可以定位触发崩溃的代码段windows下没有这么方便,但可以使用procexp和windbg来达到相同的目的,程序崩溃后,可以打开procexp,然后在procexp中选择崩溃的程序,右

斯坦福大学自然语言处理第三课“最小编辑距离(Minimum Edit Distance)”_绝对不要看眼睛里的郁金香的博客-程序员宝宝

一、课程介绍斯坦福大学于2012年3月在Coursera启动了在线自然语言处理课程,由NLP领域大牛Dan Jurafsky 和 Chirs Manning教授授课:https://class.coursera.org/nlp/以下是本课程的学习笔记,以课程PPT/PDF为主,其他参考资料为辅,融入个人拓展、注解,抛砖引玉,欢迎大家在“我爱公开课”上一起探讨学习。课件汇

七宗罪之病态的加班_普通网友的博客-程序员宝宝

0 奇怪的事情王小宝今年刚刚大学毕业,经过两轮简单的面试之后,进入了本地一家拥有20多名研发人员的IT企业,终于成为了心目中一直崇拜、向往的程序员。第一天上班,起了个大早,怀着激动的心情,迈着坚实的步伐第一个来到公司,等了十来分钟后才有人过来开门,接着是安排工位、领取入职材料,员工相互介绍,加了公司的微信群,终于入座,松了口气,心里想着,以后我就要在这个地方发光发热了,大干一场了,对自己的第一...