Как уменьшить время работы программы? C++

Как уменьшить время работы программы?
Выведите на первой строке число от 1 до n, включительно, которое имеет максимальное число делителей. На второй строке выведите число его делителей. Если есть несколько чисел от 1 до n с максимальным числом делителей, выведите любое из них.
Я для трех чисел написал исключение, но замечу что и без него все равно превышено ограничение по времени, n меньше либо равно 100000 (10^5).
Беда именно с большими числами.

#include
using namespace std;

int main()
{
int n, i, maxi = 0, a=0, k=0, j;
std::cin >> n;
if (n > 3)
{
for (i = 1; i <= n; i++)
{
k = 2;
for (j = 2; j <= i / 2; j++)
{
if (i % j == 0)
{
k++;
}
}

if (k > maxi)
{
a = i;
maxi = k;
}

}
std::cout << a << endl << maxi;
}
else if (n == 1)
{
std::cout << 1 << endl << 1;
}
else if (n == 2 or n==3)
{
std::cout << 2 << endl << 2;
}

return 0;

}