Find the number of divisors of all numbers in the range [1, n] in C++

In this problem, we are given a number N. Our task is to find the number of divisors of all numbers in the range [1, n].

Let’s take an example to understand the problem,

Input : N = 7 Output : 1 2 2 3 2 4 2

Solution Approach

A simple solution to the problem is by starting from 1 to N and for every number count the number of divisors and print them.

Example 1

Program to illustrate the working of our solution

#include <iostream> using namespace std; int countDivisor(int N){    int count = 1;    for(int i = 2; i <= N; i++){       if(N%i == 0)          count++;    }    return count; } int main(){    int N = 8;    cout<<"The number of divisors of all numbers in the range are \t";    cout<<"1 ";    for(int i = 2; i <= N; i++){       cout<<countDivisor(i)<<" ";    }    return 0; }

Output

The number of divisors of all numbers in the range are 1 2 2 3 2 4 2 4

Another approach to solve the problem is using increments of values. For this, we will create an array of size (N+1). Then, starting from 1 to N, we will check for each value i, we will increment the array value for all multiples of i less than n.

Example 2

Program to illustrate the working of our solution,

#include <iostream> using namespace std; void countDivisors(int N){    int arr[N+1];    for(int i = 0; i <= N; i++)       arr[i] = 1;       for (int i = 2; i <= N; i++) {          for (int j = 1; j * i <= N; j++)             arr[i * j]++;       }       for (int i = 1; i <= N; i++)          cout<<arr[i]<<" "; } int main(){    int N = 8;    cout<<"The number of divisors of all numbers in the range are \t"; countDivisors(N);    return 0; }

Output

The number of divisors of all numbers in the range are 1 2 2 3 2 4 2 4