HDOJ 2138 How many prime numbers

HDACM 2138

注意 不要用 j*j<=num 去循环，用j<=Math.sqrt(num)去循环，因为j*j是需要时间去计算的，会超时。

import java.util.Scanner;public class Main{public static void main(String[] args) {int next[] = new int[1000001];boolean isPirme[] = new boolean[1000000];for (int i = 2; i < isPirme.length; i++) {isPirme[i]=true;}int k = 0;for (int i = 2; i < isPirme.length; i++) {if (isPirme[i]) {next[k++] = i;for (int j = i*2; j < isPirme.length; j += i) {isPirme[j] = false;}}}
// System.out.println(Integer.MAX_VALUE);Scanner sc = new Scanner(System.in);while(sc.hasNext()){int n = sc.nextInt();int count = 0;for (int i = 0; i < n; i++) {int num = sc.nextInt();if (num>=1000000) {k=1;int j = 2;int m = (int)Math.sqrt(num);for (; j <= m ; j=next[k++]) {if (num%j==0) {break;}}if (j>m) {count++;}}else{if (isPirme[num]) {count++;}}}System.out.println(count);}sc.close();}
}