Algorithm

Problem Statement for ProperDivisors

Problem link- https://community.topcoder.com/stat?c=problem_statement&pm=8547&rd=11128

Problem Statement
     An integer k greater than 0 is called a cool divisor of m if it is less than m and divides m, but k^n does not divide m. Let d(m) denote the number of cool divisors that exist for an integer m. Given two integers a and b return the sum d(a) + d(a + 1) + ... + d(a + b).
 

Definition
    
Class: ProperDivisors
Method: analyzeInterval
Parameters: int, int, int
Returns: int
Method signature: int analyzeInterval(int a, int b, int n)
(be sure your method is public)
    
 
 

Notes
- The result will always fit into a signed 32-bit integer.
 

Constraints
- a will be between 1 and 1000000 (10^6), inclusive.
- b will be between 1 and 10000000 (10^7), inclusive.
- n will be between 2 and 10, inclusive.
 

Examples
0)  
     
32
 
1
 
3
 
Returns: 5
The cool divisors of 32 are 4, 8 and 16 so d(32) = 3; the cool divisors of 33 are 3 and 11 so d(33) = 2. Hence the desired sum d(32) + d(33) = 3 + 2 = 5.
1)  
     
1
 
12
 
2
 
Returns: 8
 
2)  
     
1000000
 
10000000
 
10
 
Returns: 146066338
 

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

class ProperDivisors {
public:
  int analyzeInterval(int a, int b, int n) {
    int e = a + b;
    long long p, res = 0;
    bool ok;
    for(int i = 1; i <= e; ++i) {
      for(int j = i * 2; j <= e; j += i) {
        p = 1;
        ok = true;
        for(int k = 0; k < n; ++k) {
          p *= i;
          if(p > j) {
            ok = false;
            break;
          }
        }
        if(ok && j % p == 0)
          continue;
        if(j >= a && j <= e)
          ++res;
      }
    }
    return res;
  }
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
32
1
3

Output

x
–
+
cmd
5
Advertisements

Demonstration

TopCoder Solution SRM394-D2-1000 Statement for ProperDivisors C,C++, Java, Js and Python ,SRM394-D2-1000,TopCoder Solution