Sign up ×
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|cite|improve this question

closed as off-topic by apnorton, Daniel Fischer, Hakim, rogerl, azimut Jul 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. – Arthur Fischer Jul 18 '14 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|cite|improve this answer
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$.

share|cite|improve this answer
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

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