How to find if a number has any odd divisor (greater than 1)?

Question

I want to build an algorithm which tells if a number has any odd divisor or not.

for example, 6 has an odd divisor 3 (greater than 1), 4 doesn't have any odd divisors, and so on.

I know that I can find all the pairs of divisors by only traversing till square root of the number.

for example, if n%i == 0 then i and n/i both are divisors.

for example, if the number given is 100 using this method I can find all the divisors and check if any divisor is odd or not i.e. 1, 100, 2, 50, 4, 25, 5, 20, 10.

Therefore this algorithms solves the problem in O(sqrt(n)) complexity. But I'm looking to optimize this.

Please comment if any more clarity is required from my side as I'm new to this forum.

Thanks !

If this is being implemented in a computer program, you can just look at the number in its binary form and ask if how many of its (non-sign) bits are $1$. If there are more than one $1$ bits then it necessarily has an odd divisor. — JMoravitz, Mar 19 '21 at 18:40
A positive integer has $1$ as its only odd divisor if and only if it is a power of $2$. — Geoffrey Trang, Mar 19 '21 at 18:50
Using logical (bitwise) operations, calculate $n \ & \ (n-1)$ If the result is not zero, $n$ has odd divisor ($n >1$) — Vasili, Mar 19 '21 at 19:22
Thank you @Vasya. If possible can you tell me how this works, I mean if possible can you share the proof so that I can understand the reason behind it. — Sreshtha Mehrotra, Mar 20 '21 at 04:59
@SreshthaMehrotra: I put more detailed explanation below. Enjoy! — Vasili, Mar 20 '21 at 12:54

Brian M. Scott · Accepted Answer · 2021-03-19T18:46:19.267

1

Just keep dividing by $2$ until you get an odd number; either it’s $1$, in which case the number is a power of $2$ and has no other positive odd divisor, or it’s an odd divisor greater than $1$. This is faster, $\Theta(\log_2n)$.

Added: And see the comment by JMoravitz for what may be an even more efficient solution, depending on just how you’re implementing the test.

edited Mar 19 '21 at 18:46

answered Mar 19 '21 at 18:37

Brian M. Scott

616,228

score 0 · Answer 2 · answered Mar 20 '21 at 12:53

The only possibility for any number $n>1$ not to have an odd divisor is for $n$ to be a power of two. In binary representation, this means that the number has only one $1$ bit and all other bits are $0$ (i.e. $4_{10}=100_2, 128_{10}=1000000_2$. Another property: the number $n-1$ will have all ones (i.e. $3_{10}=11_2, 127_{10}=111111_2$ but it will have one less digit than $n$. Thus, if you apply logical AND operation to $n \land (n-1)$, the result will be zero only if $n$ is a power of two. This is just one line of code regardless of $n$.

How to find if a number has any odd divisor (greater than 1)?

2 Answers2