Dado un número «n», encuentre el número total de divisores que son pares o impares.
Ejemplos:
Input : n = 10 Output : Even Input: n = 100 Output: Odd Input: n = 125 Output: Even
Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.
Un enfoque ingenuo sería encontrar todos los divisores y luego ver si el número total de divisores es par o impar.
La complejidad del tiempo para tal solución sería O(sqrt(n))
C++
// Naive Solution to find
// if count of divisors
// is even or odd
#include <bits/stdc++.h>
using namespace std;
// Function to count
// the divisors
void countDivisors(int n)
{
// Initialize count
// of divisors
int count = 0;
// Note that this
// loop runs till
// square root
for (int i = 1; i <= sqrt(n) + 1; i++)
{
if (n % i == 0)
// If divisors are
// equal increment
// count by one
// Otherwise increment
// count by 2
count += (n / i == i) ? 1 : 2;
}
if (count % 2 == 0)
cout << "Even" << endl;
else
cout << "Odd" << endl;
}
// Driver Code
int main()
{
cout << "The count of divisor: ";
countDivisors(10);
return 0;
}
// This code is Contributed by SHUBHAMSINGH10
C
// Naive Solution to find
// if count of divisors
// is even or odd
#include <math.h>
#include <stdio.h>
// Function to count
// the divisors
void countDivisors(int n)
{
// Initialize count
// of divisors
int count = 0;
// Note that this
// loop runs till
// square root
for (int i = 1; i <= sqrt(n) + 1; i++)
{
if (n % i == 0)
// If divisors are
// equal increment
// count by one
// Otherwise increment
// count by 2
count += (n / i == i) ? 1 : 2;
}
if (count % 2 == 0)
printf("Even\n");
else
printf("Odd\n");
}
// Driver Code
int main()
{
printf("The count of divisor: ");
countDivisors(10);
return 0;
}
Java
// Naive Solution to find if count
// of divisors is even or odd
import java.io.*;
import java.math.*;
class GFG
{
// Function to count
// the divisors
static void countDivisors(int n)
{
// Initialize count
// of divisors
int count = 0;
// Note that this
// loop runs till
// square root
for (int i = 1; i <= Math.sqrt(n) + 1; i++)
{
if (n % i == 0)
// If divisors are
// equal increment
// count by one
// Otherwise increment
// count by 2
count += (n / i == i) ? 1 : 2;
}
if (count % 2 == 0)
System.out.println("Even");
else
System.out.println("Odd");
}
// Driver Code
public static void main(String args[])
{
System.out.print("The count of divisor: ");
countDivisors(10);
}
}
// This code is contributed by Nikita Tiwari
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) :
print("Even")
else :
print("Odd")
# Driver Code
print("The count of divisor: ")
countDivisors(10)
# This code is contributed by Nikita Tiwari
C#
// C# program using Naive
// Solution to find if
// count of divisors
// is even or odd
using System;
class GFG {
// Function to count
// the divisors
static void countDivisors(int n)
{
// Initialize count
// of divisors
int count = 0;
// Note that this
// loop runs till
// square root
for (int i = 1; i <= Math.Sqrt(n)
+ 1;
i++) {
if (n % i == 0)
// If divisors are
// equal increment
// count by one
// Otherwise increment
// count by 2
count += (n / i == i) ? 1 : 2;
}
if (count % 2 == 0)
Console.Write("Even");
else
Console.Write("Odd");
}
// Driver code
public static void Main()
{
Console.Write("The count of divisor: ");
countDivisors(10);
}
}
// This code is contributed by Sam007.
PHP
<?php
// Naive Solution to
// find if count of
// divisors is even
// or odd
// Function to count
// the divisors
function countDivisors($n)
{
// Initialize count
// of divisors
$count = 0;
// Note that this
// loop runs till
// square root
for ($i = 1; $i <= sqrt($n) + 1; $i++)
{
if ($n % $i == 0)
// If divisors are
// equal increment
// count by one
// Otherwise increment
// count by 2
$count += ($n / $i == $i)? 1 : 2;
}
if ($count % 2 == 0)
echo "Even\n";
else
echo "Odd\n";
}
// Driver Code
echo "The count of divisor: ";
countDivisors(10);
// This code is contributed by ajit.
?>
Javascript
<script>
// Naive Solution to find
// if count of divisors
// is even or odd
// Function to count
// the divisors
function countDivisors(n)
{
// Initialize count
// of divisors
let count = 0;
// Note that this
// loop runs till
// square root
for (let i = 1; i <= Math.sqrt(n) + 1; i++)
{
if (n % i == 0)
// If divisors are
// equal increment
// count by one
// Otherwise increment
// count by 2
count += (Math.floor(n / i) == i) ? 1 : 2;
}
if (count % 2 == 0)
document.write("Even" + "<br>");
else
document.write("Odd" + "<br>");
}
// Driver Code
document.write("The count of divisor: ");
countDivisors(10);
// This code is contributed by Surbhi Tyagi.
</script>
Producción :
The count of divisor: Even
Complejidad temporal: O(√n)
Espacio auxiliar: O(1)
Solución Eficiente:
Podemos observar que el número de divisores es impar solo en el caso de los cuadrados perfectos. Por lo tanto, la mejor solución sería verificar si el número dado es un cuadrado perfecto o no. Si es un cuadrado perfecto, entonces el número de divisores sería impar, de lo contrario sería par.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program for
// Efficient Solution to find
// if count of divisors is
// even or odd
#include <bits/stdc++.h>
using namespace std;
// Function to find if count
// of divisors is even or
// odd
void countDivisors(int n)
{
int root_n = sqrt(n);
// If n is a perfect square,
// then it has odd divisors
if (root_n * root_n == n)
printf("Odd\n");
else
printf("Even\n");
}
// Driver Code
int main()
{
cout << "The count of divisors"
<< " of 10 is: ";
countDivisors(14);
return 0;
}
Java
// Java program for Efficient
// Solution to find if count of
// divisors is even or odd
import java.io.*;
import java.math.*;
class GFG
{
// Function to find if count
// of divisors is even or
// odd
static void countDivisors(int n)
{
int root_n = (int)(Math.sqrt(n));
// If n is a perfect square,
// then, it has odd divisors
if (root_n * root_n == n)
System.out.println("Odd");
else
System.out.println("Even");
}
// Driver code
public static void main(String args[])
throws IOException
{
System.out.print("The count of" +
"divisors of 10 is: ");
countDivisors(10);
}
}
// This code is contributed by Nikita Tiwari
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:
print('Odd')
else:
print('Even')
# Driver code
if __name__ == '__main__':
print("The count of divisor is:")
NumOfDivisor(14)
# This code is contributed by Yt R
C#
// C# program for efficient
// solution to find of
// count of divisors is
// even or odd
using System;
class GFG {
// Function to find if
// count of divisors
// is even or odd
static void countDivisors(int n)
{
int root_n = (int)(Math.Sqrt(n));
// If n is a perfect square,
// then, it has odd divisors
if (root_n * root_n == n)
Console.WriteLine("Odd");
else
Console.WriteLine("Even");
}
// Driver code
public static void Main()
{
Console.Write("The count of divisors : ");
countDivisors(10);
}
}
// This code is contributed by Sam007.
PHP
<?php
// Php program for Efficient
// Solution to find if count of
// divisors is even or odd
// Function to find if count
// of divisors is even or
// odd
function countDivisors($n)
{
$root_n = sqrt($n);
// If n is a perfect square,
// then it has odd divisors
if ($root_n * $root_n == $n)
echo "Odd\n";
else
echo "Even\n";
}
// Driver Code
echo "The count of divisors of 10 is: ";
countDivisors(10);
// This code is contributed by ajit
?>
Javascript
<script>
// JavaScript program for
// Efficient Solution to find
// if count of divisors
// is even or odd
// Function to count
// the divisors
function countDivisors(n)
{
// Store square root of n
let root_n = Math.sqrt(n);
// If n is a perfect square,
// then it has odd divisors
if (root_n * root_n == n)
document.write("Odd" + "<br>");
else
document.write("Even" + "<br>");
}
// Driver Code
document.write("The count of divisor: ");
countDivisors(10);
// This code is contributed by Surbhi Tyagi.
</script>
Producción :
The count of divisor: Even
Complejidad temporal: O(√n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Aarti_Rathi y Ashutosh Kumar . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA