TopCoder problem "SmoothNumbersHard" used in SRM 388 (Division II Level Three)



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

Writer:

bmerry

Testers:

PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

Problem categories:

Math