# What is the efficient way to calculate number of divisors of N that are divisible by 2?. [closed]

For example if a number is given let say 8 then its factors are 1,2,4,8 hence total numbers of divisors which are divisible by 2 are (2,4,8) that is 3.

-

## closed as off-topic by apnorton, Daniel Fischer♦, Hakim, rogerl, azimutJul 11 '14 at 22:19

• This question does not appear to be about math within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

What have you tried so far? :) – Shauna Jul 11 '14 at 16:24
I'm checking if a number is a factor and is also divisible by 2 then count, but I want efficient method for this. – The L Jul 11 '14 at 16:26
Hello and welcome. Can you do a similar problem? E.g. can you compute efficiently the number of all divisors of an number $N$? – Hans Engler Jul 11 '14 at 16:40
This question is strongly related to a problem from HackerRank's "Math Programming Contest July '14" (problem link), which has now ended. – arjafi Jul 18 '14 at 17:27

## 2 Answers

Simply count the number of divisors of ${n\over 2}$. If

$$n=2^\alpha p_1^{e_1}\ldots p_n^{e_n}$$ is the prime factorization of $n$ then

$$\tau\left({n\over 2}\right)=\alpha(e_1+1)(e_2+1)\ldots (e_n+1)$$

This even agrees when $n$ is odd, i.e. $\alpha=0$.

-
How will do this in Programming? – The L Jul 11 '14 at 16:31
You would have to tell it to find the prime factorization of $n$, a hard problem in general, but then it's equivalent to finding all the divisors, so there's no "easy" way to do it, unless you can prove GRH. – Adam Hughes Jul 11 '14 at 16:36
List<int> Fact2(int val) { if (val % 2 == 1) return new List<int>(); List<int> dividors = new List<int>(); for (int i = 1; i < val >> 1; i++) if (val % i == 0) dividors.Add(i<<1); return dividors; } – Seb Jul 11 '14 at 19:36
@Seb That is still $\mathcal{\Theta}(n)$, and thus not the efficient one can do. And what's with the bitshifts? (Modern compilers don't need that much help from the programmer for optimization) – apnorton Jul 11 '14 at 21:59
agree @anorton numbers ranges from 1 to 10^9, so Θ(n) won't work here. – The L Jul 12 '14 at 1:01

Hint: Do you know how to calculate the number of divisors of a number from its prime factorization? Now you require the exponent of $2$ to be at least $1$.

-
no sir, I don't know how to do this please explain. – The L Jul 11 '14 at 16:26
You could see this article The line under Properties that starts $\sigma_0(n)$ is the one you want. – Ross Millikan Jul 11 '14 at 21:06