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: SmoothNumbers 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 100,000, inclusive.
-k will be between 1 and 100, inclusive.

Examples

0)

 10 3
Returns: 7
 Of the first ten integers, only 5, 7 and 10 have prime factors greater than 3.
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)

 100000 100
Returns: 17442

Problem url:

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

Problem stats url:

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

bmerry

Testers:

PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

Problem categories:

Brute Force, Simple Math