TopCoder problem "SmoothNumbers" used in SRM 388 (Division I Level One)



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

Writer:

bmerry

Testers:

PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

Problem categories:

Brute Force, Simple Math