### Problem Statement

A positive integer is said to be k-smooth if its largest prime factor is no greater than k. Compute how many positive integers less than or equal to N are k-smooth.

### Definition

 Class: SmoothNumbersHard Method: countSmoothNumbers Parameters: int, int Returns: int Method signature: int countSmoothNumbers(int N, int k) (be sure your method is public)

### Constraints

-N will be between 1 and 5,000,000, inclusive.
-k will be between 1 and 1,000, inclusive.

### Examples

0)

 `10` `3`
`Returns: 7`
 Of the first ten positive integers, only 5, 7 and 10 have prime factors greater than 3; the rest are 3-smooth.
1)

 `10` `4`
`Returns: 7`
 4 is not prime, so 4-smooth numbers are the same as 3-smooth numbers.
2)

 `15` `3`
`Returns: 8`
3)

 `5` `20`
`Returns: 5`
4)

 `123456` `123`
`Returns: 23855`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8565

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11122&pm=8565

bmerry

#### Testers:

PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

Math