Write a C ++ function that determines the number of uneven divisors of a natural number transmitted as a parameter.

Question

Write a C ++ function (named "nr_div_imp") that determines the number of uneven divisors (1, 3, 5...) of a natural number transmitted as a parameter. The function returns the result via an output parameter.

This is my ideea, but I need to make it faster. Ideeas are highly appreciated. 😅✨

#include <iostream>

using namespace std;

void nr_div_imp(int n, int &k)
{ k=0;
for(int d=1;d<=n;d+=2)
if(n%d==0)
k=k+1;
}

Answer 1

https://code.sololearn.com/cB37rbIlL1gl/?ref=app

Answer 2

You can first divide your number n by the largest power of 2 it is divisible by - you'll get an odd number m, which has the same odd divisors as n. Then you can loop (with step 2) from 1 up to int(sqrt(m)), counting each found divisor twice: for each divisor a < sqrt(m) there would be a divisor n/a > sqrt(m). Finally if sqrt(m) is integer, it means you counted it twice, so you should reduce the result by 1

This way the complexity of your function would be O(sqrt(n)) instead of linear.