Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

closed as off-topic by anorton, Daniel Fischer, Hakim, rogerl, azimut Jul 11 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? :) –  Shaun Jul 11 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. –  Blackhat002 Jul 11 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 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. –  Arthur Fischer Jul 18 at 17:27

2 Answers 2

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$.

share|improve this answer
How will do this in Programming? –  Blackhat002 Jul 11 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 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 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) –  anorton Jul 11 at 21:59
agree @anorton numbers ranges from 1 to 10^9, so Θ(n) won't work here. –  Blackhat002 Jul 12 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$.

share|improve this answer
no sir, I don't know how to do this please explain. –  Blackhat002 Jul 11 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 at 21:06

Not the answer you're looking for? Browse other questions tagged or ask your own question.