# 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.

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


+ 订阅