Gotta Catch 'Em All

In Pallet town of the Kanto region, there lived a young boy named Ash Ketchum. Ash loves Pokemon and has a dream of becoming a Pokemon Master. He is about to start his Pokemon journey so he reaches to Professor Oak to get his first starter Pokemon. Before giving Ash his starter Pokemon, Professor Oak needs to check whether he is capable of raising a Pokemon or not. So, the professor gave him a task to test his knowledge about Pokemon. The task is as follows:

Each Pokemon can be represented by a unique ID number and its strength is equivalent to the total number of factors (including 1 and number itself) of its ID number. In a Pokemon battle, a Pokemon with higher strength will always win a battle against a Pokemon with lower strength. Let the total number of Pokemon's in Kanto region be N(their ID ranging from 1 to N). Given a Pokemon ID number K. Find the total number of Pokemon, the given Pokemon can certainly beat.

Example:

Input:  n = 8, k = 4
Output: 5

Approach

C++

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

int main()
{
    int n = 8;
    int k = 4;
    int sum = 0, id, strength, size;
    size = n;
    int divArr[n + 1] = {0};
    for (int i = 1; i <= size; ++i)
    {
        for (int j = i; j <= size; j += i)
            ++divArr[j];
    }

    int arr[n + 1] = {0};
    int win[n + 1] = {0};
    for (int i = 1; i <= n; ++i)
    {
        strength = divArr[i];
        ++arr[strength];
    }
    for (int i = 1; i <= n; ++i)
    {
        win[i] = sum;
        sum += arr[i];
    }

    strength = divArr[k];
    cout << win[strength] << "\n";
    return 0;
}