C++ program to find numbers with K odd divisors in a given range

In this problem, we are given three integer values, L, R, and k. Our task is to find numbers with K divisors in a given range. We will be finding the count of numbers in the range [L, R] that have exactly k divisors. We will be counting the 1 and the number itself as a divisor.

Let’s take an example to understand the problem,

Input

a = 3, b = 10, k = 4

Output

2

Explanation

Numbers with exactly 3 divisors within the range 3 to 10 are 6 : divisors = 1, 2, 3, 6 8 : divisors = 1, 2, 4, 8

Solution Approach

A simple solution to the problem is by counting the k divisors.. So, we will count the number of divisors for all numbers in the range. And if the count of divisors in k, we will add 1 to the number count.

Program to illustrate the working of our solution,

Example

 Live Demo

#include<bits/stdc++.h> using namespace std; int countDivisors(int n) {    int divisors = 0;    for (int i=1; i<=sqrt(n)+1; i++) {       if (n%i==0) {          divisors++;          if (n/i != i)             divisors ++;       }    }    return divisors; } int countNumberKDivisors(int a,int b,int k) {    int numberCount = 0;    for (int i=a; i<=b; i++) {       if (countDivisors(i) == k)          numberCount++;    }    return numberCount; } int main() {    int a = 3, b = 10, k = 4;    cout<<"The count of numbers with "<<k<<" divisors is "<<countNumberKDivisors(a, b, k);    return 0; }

Output

The count of numbers with 4 divisors is 2