Count the numbers < N which have equal number of divisors as K in C++

We are given two numbers N and K. The goal is to find the count of numbers between 1 and N that have divisors equal to the divisors of K in range [1,N].

We will first count the divisors of K in range [1,N] and store in variable count.

Now we will start from i=1 to i=N. Now for each number num=i (such that i!=K), count divisors of num in range[1,N]. And store their occurrences in variable divisors.

If divisors=count means num has the same divisors as K in range [1,N]. increment count of such numbers.

Let’s understand with examples.

Input − N=5, K=2

Output − Count of numbers <N which have equal divisors as K − 1

Explanation −

Between 1 and 5, 2 has divisors 1,2 only. count=2 1 has only 1 divisor which is 1 3 has divisors 1,3 → 2 4 has divisors 1,2,4 → 3 1 number 3 has 2 divisors like K=2.

Input − N=15, K=10

Output − Count of numbers <N which have equal divisors as K − 3

Explanation −

Between 1 and 15, 10 has divisors 1,10 only. count=2 Similarly 6, 8, 14 have only 2 divisors.

Approach used in the below program is as follows

• We take N and K as integers.

• Function countDivisibles(int n, int k,) takes N and K as parameters and returns the count of numbers between < N that have equal divisors as K.

• Take the initial count as 0. For the number of divisors<n of k.

• Take the initial numcount as 0. For the numbers that have the same divisors as k.

• Using for loop, start from i=1 to i<n. If k%i==0 then increment count.

• Now count has number of divisors of k that are <n

• Again using for loop, start from i=1 to i<n. For each num=i (such that it is not equal to k ) take initial count of divisors as variable divisors which is 0.

• Now between i=1 and i<n find if num%i==0 if yes increment divisors. At the end divsors will have a number of divisors of num that are <n.

• Check if divisors=count. If true increment variable numcount which stores count of numbers <n which have equal divisors as k.

• Return numcount as result in the end of both loops.

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; int countDivisibles(int n, int k){    int count = 0;    int numcount=0;    for (int i = 1; i < n;i++ ){       if (k % i == 0)          { count++; }    }    //now count has number of divisors of k    // cout<<count<<endl;    for(int i=1;i<n;i++){       int num;       if(i!=k){          num=i;          int divisors=0;          for(int j=1;j<n;j++){             if(num%j==0)                { divisors++; }          }          //cout<<endl<<num<<" "<<divisors;          if(divisors==count)             { numcount++; }          }       }    return numcount; } int main(){    int N = 50, K = 6;    cout<<endl<<"Numbers < N which have equal divisors as K:"<<countDivisibles(N,K);    return 0; }

Output

If we run the above code it will generate the following output −

Numbers < N which have equal divisors as K:14