TopCoder problem "RefactorableNumber" used in SRM 343 (Division I Level Three)



Problem Statement

    A refactorable number is defined to be a number that is divisble by the number of distinct factors that it has. Examples of refactorable numbers include 1 (1 factor), 12 (6 factors), and 9 (3 factors), but not 7 (2 factors) or 16 (5 factors).

You will be given two ints, low and high. Return the number of refactorable numbers between low and high, inclusive.

 

Definition

    
Class:RefactorableNumber
Method:count
Parameters:int, int
Returns:int
Method signature:int count(int low, int high)
(be sure your method is public)
    
 

Constraints

-low will be between 1 and 2,000,000, inclusive.
-high will be between low and 2,000,000, inclusive.
 

Examples

0)
    
1
10
Returns: 4
There are 4 refactorable numbers between 1 and 10, namely: 1, 2, 8, and 9.
1)
    
10
100
Returns: 12
2)
    
25
35
Returns: 0
3)
    
123
4567
Returns: 315

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10667&pm=6784

Writer:

connect4

Testers:

PabloGilberto , brett1479 , Olexiy , lovro

Problem categories:

Brute Force, Math