Python Program for Check if count of divisors is even or odd
Write a Python program for a given number “n”, the task is to find its total number of divisors that are even or odd.
Examples:
Input : n = 10
Output: EvenInput: n = 100
Output: OddInput: n = 125
Output: EvenPython Program for Check if count of divisors is even or odd using Naive Approach:
A naive approach would be to find all the divisors and then see if the total number of divisors is even or odd.
Below is the implementation of the approach:
Python3
# Naive Solution to find if count
# of divisors is even or odd
import
math
# Function to count
# the divisors
def
countDivisors(n) :
# Initialize count
# of divisors
count
=
0
# Note that this loop
# runs till square
# root
for
i
in
range
(
1
, (
int
)(math.sqrt(n))
+
2
) :
if
(n
%
i
=
=
0
) :
# If divisors are
# equal, increment
# count by one
# Otherwise increment
# count by 2
if
( n
/
/
i
=
=
i) :
count
=
count
+
1
else
:
count
=
count
+
2
if
(count
%
2
=
=
0
) :
(
"Even"
)
else
:
(
"Odd"
)
# Driver Code
(
"The count of divisor: "
)
countDivisors(
10
)
# This code is contributed by Nikita Tiwari
OutputThe count of divisor: EvenTime Complexity: O(√n)
Auxiliary Space: O(1)Efficient Solution:
We can observe that the number of divisors is odd only in case of perfect squares. Hence the best solution would be to check if the given number is perfect square or not. If it’s a perfect square, then the number of divisors would be odd, else it’d be even.
Below is the implementation of the above approach:
Python3
# Python program for
# Efficient Solution to find
# find if count of divisors
# is even or odd
import
math
def
NumOfDivisor(n):
if
n <
1
:
return
root_n
=
int
(math.sqrt(n))
# If n is a perfect square,
# then it has odd divisors
if
root_n
*
*
2
=
=
n:
(
'Odd'
)
else
:
(
'Even'
)
# Driver code
if
__name__
=
=
'__main__'
:
(
"The count of divisor is:"
)
NumOfDivisor(
14
)
# This code is contributed by Yt R
OutputThe count of divisor is: EvenTime Complexity: O(logn) as it is using inbuilt sqrt function
Auxiliary Space: O(1)Python Program for Check if count of divisors is even or odd using factorization:
- Find the prime factorization of the given number n.
- Count the number of times each distinct prime factor appears in the factorization. This count is equal to the exponent of the prime factor in the factorization.
- Compute the product of (exponent + 1) for each distinct prime factor.
- If the product is even, then the number of divisors is even, otherwise it is odd.
Below is the implementation of the above approach:
Python3
# Added by ~Nikunj Sonigara
def
prime_factors(n):
factors
=
[]
while
n
%
2
=
=
0
:
factors.append(
2
)
n
/
/
=
2
for
i
in
range
(
3
,
int
(n
*
*
0.5
)
+
1
,
2
):
while
n
%
i
=
=
0
:
factors.append(i)
n
/
/
=
i
if
n >
2
:
factors.append(n)
return
factors
def
count_divisors(n):
factors
=
prime_factors(n)
prev
=
factors[
0
]
count
=
1
product
=
1
for
i
in
range
(
1
,
len
(factors)):
if
factors[i]
=
=
prev:
count
+
=
1
else
:
product
*
=
(count
+
1
)
prev
=
factors[i]
count
=
1
product
*
=
(count
+
1
)
if
product
%
2
=
=
0
:
return
"Even"
else
:
return
"Odd"
if
__name__
=
=
"__main__"
:
(count_divisors(
10
))
# Output: Even
(count_divisors(
100
))
# Output: Odd
(count_divisors(
125
))
# Output: Even
OutputEven Odd EvenTime Complexity: O(sqrt(n)), where n is the input number.|
Auxiliary space: O(1)Please refer complete article on Check if count of divisors is even or odd for more details!