SRM 388 Level2 1000
http://www.topcoder.com/stat?c=problem_statement&pm=8565&rd=11122
给定N和K，返回N中最大素数因子小于等于K的数字个数

解法与素数的计算流程相通
自下向上，只是对每个数多记录一次其最大素数因子
 1mport java.util.*;
 2import java.util.regex.*;
 3import java.text.*;
 4import java.math.*;
 5import java.awt.geom.*;
 6
 7public class SmoothNumbersHard
 8{
 9    public int countSmoothNumbers(int N, int k)
10    {
11        boolean[] prime = new boolean[N+1];
12        int[] divider = new int[N+1];
13        Arrays.fill(prime,true);
14        Arrays.fill(divider, 1);
15        for(int i = 2 ; i <= N; ++ i){
16            if(prime[i]){
17                divider[i] = i;
18                for(int j = 2; i * j <= N; ++ j){
19                    prime[i*j] = false;
20                    divider[i*j] = i;
21                }
22            }
23        }
24        int ans = 0;
25        for(int i = 1 ; i <= N ; ++ i){
26            if(divider[i] <= k)
27                ans++;
28        }
29        return ans;
30    }
31