HDOJ(HDU) 2138 How many prime numbers(素数-快速筛选没用上、)-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

HDOJ(HDU) 2138 How many prime numbers(素数-快速筛选没用上、)

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

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];
                }
            }
        }
    }
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: