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

谙忆

发布于 2021-01-21 15:41:26

2290

发布于 2021-01-21 15:41:26

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016/05/05 ，如有侵权请联系 cloudcommunity@tencent.com 删除

case