Number of divisors

You are given two numbers n and k. For each number in the interval [1, n], your task is to calculate its largest divisor that is not divisible by k. Print the sum of these divisors.

Note: k is a prime number.

Example:

Input:  n = 10 , k=3
Output: 41

Approach

Java

public class NumberOfDivisors {
    public static void main(String args[]) {
        int n = 10;
        int k = 3;
        long output = calculateSumWithoutK(n, k);
        System.out.print(output);
    }

    private static long calculateSumWithoutK(int n, int k) {
        long sum = ((long) n * (n + 1)) >> 1;
        if (n < k) {
            return sum;
        }
        int noOfK = ((n - k) / k) + 1;
        sum -= k * (((long) noOfK * (noOfK + 1)) >> 1);
        sum += calculateSumWithoutK(noOfK, k);
        return sum;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

long long res;
long long numOfDivisors(long long n, long long k)
{

    res = res - k * (n * (n + 1) / 2) + n * (n + 1) / 2;
    n = n / k;
    if (n == 0)
        return res;
    return numOfDivisors(n, k);
}
int main()
{

    long long n = 10, k = 3;
    res = (n * (n + 1)) / 2;
    n = n / k;
    cout << numOfDivisors(n, k) << "\n";
    return 0;
}