HDOJ 2136 Largest prime factor

HDACM 2136

打表，只要是素数计数++，并且更新是该素数倍数的所有数的值

import java.util.Scanner;public class Main{public static void main(String[] args) {int prime[] = new int[1000000];int count = 0;for (int i = 2; i < prime.length; i++) {if (prime[i] == 0) {count++;prime[i] = count;for (int j = i * 2; j < prime.length; j += i) {prime[j] = count;}}}Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int n = sc.nextInt();System.out.println(prime[n]);}sc.close();}
}