Dado un número n, cuente todos los divisores distintos de él.
Ejemplos:
Input : 18 Output : 6 Divisors of 18 are 1, 2, 3, 6, 9 and 18. Input : 100 Output : 9 Divisors of 100 are 1, 2, 4, 5, 10, 20, 25, 50 and 100
Enfoque 1:
Una solución ingenua sería iterar todos los números desde 1 hasta sqrt(n), comprobando si ese número divide n e incrementando el número de divisores. Este enfoque requiere tiempo O(sqrt(n)).
C++
// C implementation of Naive method to count all
// divisors
#include <bits/stdc++.h>
using namespace std;
// function to count the divisors
int countDivisors(int n)
{
int cnt = 0;
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
// If divisors are equal,
// count only one
if (n / i == i)
cnt++;
else // Otherwise count both
cnt = cnt + 2;
}
}
return cnt;
}
/* Driver program to test above function */
int main()
{
printf("Total distinct divisors of 100 are : %d",
countDivisors(100));
return 0;
}
Java
// JAVA implementation of Naive method
// to count all divisors
import java.io.*;
import java.math.*;
class GFG {
// function to count the divisors
static int countDivisors(int n)
{
int cnt = 0;
for (int i = 1; i <= Math.sqrt(n); i++)
{
if (n % i == 0) {
// If divisors are equal,
// count only one
if (n / i == i)
cnt++;
else // Otherwise count both
cnt = cnt + 2;
}
}
return cnt;
}
/* Driver program to test above function */
public static void main(String args[])
{
System.out.println("Total distinct "
+ "divisors of 100 are : "
+ countDivisors(100));
}
}
/*This code is contributed by Nikita Tiwari.*/
Python3
# Python3 implementation of Naive method
# to count all divisors
import math
# function to count the divisors
def countDivisors(n) :
cnt = 0
for i in range(1, (int)(math.sqrt(n)) + 1) :
if (n % i == 0) :
# If divisors are equal,
# count only one
if (n / i == i) :
cnt = cnt + 1
else : # Otherwise count both
cnt = cnt + 2
return cnt
# Driver program to test above function */
print("Total distinct divisors of 100 are : ",
countDivisors(100))
# This code is contributed by Nikita Tiwari.
C#
// C# implementation of Naive method
// to count all divisors
using System;
class GFG {
// function to count the divisors
static int countDivisors(int n)
{
int cnt = 0;
for (int i = 1; i <= Math.Sqrt(n);
i++)
{
if (n % i == 0) {
// If divisors are equal,
// count only one
if (n / i == i)
cnt++;
// Otherwise count both
else
cnt = cnt + 2;
}
}
return cnt;
}
// Driver program
public static void Main()
{
Console.WriteLine("Total distinct"
+ " divisors of 100 are : "
+ countDivisors(100));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP implementation of Naive
// method to count all divisors
// function to count the divisors
function countDivisors($n)
{
$cnt = 0;
for ($i = 1; $i <= sqrt($n); $i++)
{
if ($n % $i == 0)
{
// If divisors are equal,
// count only one
if ($n / $i == $i)
$cnt++;
// Otherwise count both
else
$cnt = $cnt + 2;
}
}
return $cnt;
}
// Driver Code
echo "Total distinct divisors of 100 are : ",
countDivisors(100);
// This code is contributed by Ajit
?>
Javascript
<script>
// JavaScript program for the above approach
// function to count the divisors
function countDivisors(n)
{
let cnt = 0;
for (let i = 1; i <= Math.sqrt(n); i++)
{
if (n % i == 0) {
// If divisors are equal,
// count only one
if (n / i == i)
cnt++;
else // Otherwise count both
cnt = cnt + 2;
}
}
return cnt;
}
// Driver Code
document.write("Total distinct "
+ "divisors of 100 are : "
+ countDivisors(100));
// This code is contributed by susmitakundugoaldanga.
</script>
Producción :
Total distinct divisors of 100 are : 9
Complejidad del tiempo: (O(n^1/2))
Complejidad espacial: O(1)
Enfoque 2:
solución optimizada (O(n^1/3))
Para un número N, tratamos de encontrar un número X ≤ ∛N, es decir, X^3 ≤ N tal que divida al número, y otro número Y tal que N = X * Y. X consiste en todos los factores primos de N, que son menores que ∛N e Y contiene todos los factores primos que son mayores. Por lo tanto, no tienen factor común y su HCF es 1.
Iteramos a través de los números 1 a ∛N, y para todos los números primos, verificamos si el número divide a N.
Si el primo es divisible, lo dividimos tantas veces como podamos del número N, de modo que ya no quede ningún factor primo específico. Seguimos haciendo esto para todos los factores primos menores que ∛N. Por lo tanto, el número que queda después del bucle no tendrá factores primos menores que ∛N.
Para N = p1 e1 *p2 e2 *p3 e3 … donde p1, p2, p3.. son los factores primos, el número de divisores está dado por (e1+1) * (e2+1) * (e3+1) …
El bucle for nos da el producto de (e+1) para cada factor primo menor que ∛N.
El número restante solo puede tener un máximo de 2 factores primos. Probaremos esto por contradicción.
Asuma Y = p1 * p2 * p3 donde p1,p2,p3 son primos y p1,p2,p3 > ∛N [Explicado anteriormente].
Como p1 >∛N y p2 > ∛N y p3 > ∛N
p1*p2*p3 > ∛N*∛N*∛N
=> p1*p2*p3 > N. Pero Y es un factor de N y no puede ser mayor que N.
Por tanto, hay una contradicción, que implica que uno de p1, p2, p3 debe ser menor que ∛N.
Pero como todos los números primos menores que ∛N han sido absorbidos por X, esto no es posible.
Entonces, Y no puede tener más de 2 factores primos.
Y puede por lo tanto tener:
1 factores primos si es primo (Y) con exponente 1
1 factores primos si es un cuadrado de un número primo (sqrt(Y)), con exponente 2
2 factores primos si compuesto (p1, p2) con exponente 1 y 1
Por lo tanto, multiplicamos:
Si Y es primo => (exponente de y .ie 1 +1) = 2
Si Y es un cuadrado de primo => (exponente de sqrt(y) .ie 2+1) = 3
Si Y es compuesto => (exponente de p1+1)*(exponente de p2+1) = 2 * 2 = 4
C++
// C++ program to count distinct divisors
// of a given number n
#include <bits/stdc++.h>
using namespace std;
void SieveOfEratosthenes(int n, bool prime[],
bool primesquare[], int a[])
{
//For more details check out: https://www.geeksforgeeks.org/sieve-of-eratosthenes/
// Create a boolean array "prime[0..n]" and
// initialize all entries it as true. A value
// in prime[i] will finally be false if i is
// Not a prime, else true.
for (int i = 2; i <= n; i++)
prime[i] = true;
// Create a boolean array "primesquare[0..n*n+1]"
// and initialize all entries it as false. A value
// in squareprime[i] will finally be true if i is
// square of prime, else false.
for (int i = 0; i <= (n * n + 1); i++)
primesquare[i] = false;
// 1 is not a prime number
prime[1] = false;
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed, then
// it is a prime
if (prime[p] == true) {
// Update all multiples of p starting from p * p
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
int j = 0;
for (int p = 2; p <= n; p++) {
if (prime[p]) {
// Storing primes in an array
a[j] = p;
// Update value in primesquare[p*p],
// if p is prime.
primesquare[p * p] = true;
j++;
}
}
}
// Function to count divisors
int countDivisors(int n)
{
// If number is 1, then it will have only 1
// as a factor. So, total factors will be 1.
if (n == 1)
return 1;
bool prime[n + 1], primesquare[n * n + 1];
int a[n]; // for storing primes upto n
// Calling SieveOfEratosthenes to store prime
// factors of n and to store square of prime
// factors of n
SieveOfEratosthenes(n, prime, primesquare, a);
// ans will contain total number of distinct
// divisors
int ans = 1;
// Loop for counting factors of n
for (int i = 0;; i++) {
// a[i] is not less than cube root n
if (a[i] * a[i] * a[i] > n)
break;
// Calculating power of a[i] in n.
int cnt = 1; // cnt is power of prime a[i] in n.
while (n % a[i] == 0) // if a[i] is a factor of n
{
n = n / a[i];
cnt = cnt + 1; // incrementing power
}
// Calculating the number of divisors
// If n = a^p * b^q then total divisors of n
// are (p+1)*(q+1)
ans = ans * cnt;
}
// if a[i] is greater than cube root of n
// First case
if (prime[n])
ans = ans * 2;
// Second case
else if (primesquare[n])
ans = ans * 3;
// Third case
else if (n != 1)
ans = ans * 4;
return ans; // Total divisors
}
// Driver Program
int main()
{
cout << "Total distinct divisors of 100 are : "
<< countDivisors(100) << endl;
return 0;
}
Java
// JAVA program to count distinct
// divisors of a given number n
import java.io.*;
class GFG {
static void SieveOfEratosthenes(int n, boolean prime[],
boolean primesquare[], int a[])
{
// Create a boolean array "prime[0..n]" and
// initialize all entries it as true. A value
// in prime[i] will finally be false if i is
// Not a prime, else true.
for (int i = 2; i <= n; i++)
prime[i] = true;
/* Create a boolean array "primesquare[0..n*n+1]"
and initialize all entries it as false.
A value in squareprime[i] will finally
be true if i is square of prime,
else false.*/
for (int i = 0; i < ((n * n) + 1); i++)
primesquare[i] = false;
// 1 is not a prime number
prime[1] = false;
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= n; i += p)
prime[i] = false;
}
}
int j = 0;
for (int p = 2; p <= n; p++) {
if (prime[p]) {
// Storing primes in an array
a[j] = p;
// Update value in
// primesquare[p*p],
// if p is prime.
primesquare[p * p] = true;
j++;
}
}
}
// Function to count divisors
static int countDivisors(int n)
{
// If number is 1, then it will
// have only 1 as a factor. So,
// total factors will be 1.
if (n == 1)
return 1;
boolean prime[] = new boolean[n + 1];
boolean primesquare[] = new boolean[(n * n) + 1];
// for storing primes upto n
int a[] = new int[n];
// Calling SieveOfEratosthenes to
// store prime factors of n and to
// store square of prime factors of n
SieveOfEratosthenes(n, prime, primesquare, a);
// ans will contain total number
// of distinct divisors
int ans = 1;
// Loop for counting factors of n
for (int i = 0;; i++) {
// a[i] is not less than cube root n
if (a[i] * a[i] * a[i] > n)
break;
// Calculating power of a[i] in n.
// cnt is power of prime a[i] in n.
int cnt = 1;
// if a[i] is a factor of n
while (n % a[i] == 0) {
n = n / a[i];
// incrementing power
cnt = cnt + 1;
}
// Calculating the number of divisors
// If n = a^p * b^q then total
// divisors of n are (p+1)*(q+1)
ans = ans * cnt;
}
// if a[i] is greater than cube root
// of n
// First case
if (prime[n])
ans = ans * 2;
// Second case
else if (primesquare[n])
ans = ans * 3;
// Third case
else if (n != 1)
ans = ans * 4;
return ans; // Total divisors
}
// Driver Program
public static void main(String args[])
{
System.out.println("Total distinct divisors"
+ " of 100 are : " + countDivisors(100));
}
}
/*This code is contributed by Nikita Tiwari*/
Python3
# Python3 program to count distinct
# divisors of a given number n
def SieveOfEratosthenes(n, prime,primesquare, a):
# Create a boolean array "prime[0..n]"
# and initialize all entries it as
# true. A value in prime[i] will finally
# be false if i is not a prime, else true.
for i in range(2,n+1):
prime[i] = True
# Create a boolean array "primesquare[0..n*n+1]"
# and initialize all entries it as false.
# A value in squareprime[i] will finally be
# true if i is square of prime, else false.
for i in range((n * n + 1)+1):
primesquare[i] = False
# 1 is not a prime number
prime[1] = False
p = 2
while(p * p <= n):
# If prime[p] is not changed,
# then it is a prime
if (prime[p] == True):
# Update all multiples of p
i = p * 2
while(i <= n):
prime[i] = False
i += p
p+=1
j = 0
for p in range(2,n+1):
if (prime[p]==True):
# Storing primes in an array
a[j] = p
# Update value in primesquare[p*p],
# if p is prime.
primesquare[p * p] = True
j+=1
# Function to count divisors
def countDivisors(n):
# If number is 1, then it will
# have only 1 as a factor. So,
# total factors will be 1.
if (n == 1):
return 1
prime = [False]*(n + 2)
primesquare = [False]*(n * n + 2)
# for storing primes upto n
a = [0]*n
# Calling SieveOfEratosthenes to
# store prime factors of n and to
# store square of prime factors of n
SieveOfEratosthenes(n, prime, primesquare, a)
# ans will contain total
# number of distinct divisors
ans = 1
# Loop for counting factors of n
i=0
while(1):
# a[i] is not less than cube root n
if(a[i] * a[i] * a[i] > n):
break
# Calculating power of a[i] in n.
cnt = 1 # cnt is power of
# prime a[i] in n.
while (n % a[i] == 0): # if a[i] is a factor of n
n = n / a[i]
cnt = cnt + 1 # incrementing power
# Calculating number of divisors
# If n = a^p * b^q then total
# divisors of n are (p+1)*(q+1)
ans = ans * cnt
i+=1
# if a[i] is greater than
# cube root of n
n=int(n)
# First case
if (prime[n]==True):
ans = ans * 2
# Second case
else if (primesquare[n]==True):
ans = ans * 3
# Third case
else if (n != 1):
ans = ans * 4
return ans # Total divisors
# Driver Code
if __name__=='__main__':
print("Total distinct divisors of 100 are :",countDivisors(100))
# This code is contributed
# by mits
C#
// C# program to count distinct
// divisors of a given number n
using System;
class GFG {
static void SieveOfEratosthenes(int n, bool[] prime,
bool[] primesquare, int[] a)
{
// Create a boolean array "prime[0..n]" and
// initialize all entries it as true. A value
// in prime[i] will finally be false if i is
// Not a prime, else true.
for (int i = 2; i <= n; i++)
prime[i] = true;
/* Create a boolean array "primesquare[0..n*n+1]"
and initialize all entries it as false.
A value in squareprime[i] will finally
be true if i is square of prime,
else false.*/
for (int i = 0; i < ((n * n) + 1); i++)
primesquare[i] = false;
// 1 is not a prime number
prime[1] = false;
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= n; i += p)
prime[i] = false;
}
}
int j = 0;
for (int p = 2; p <= n; p++) {
if (prime[p]) {
// Storing primes in an array
a[j] = p;
// Update value in
// primesquare[p*p],
// if p is prime.
primesquare[p * p] = true;
j++;
}
}
}
// Function to count divisors
static int countDivisors(int n)
{
// If number is 1, then it will
// have only 1 as a factor. So,
// total factors will be 1.
if (n == 1)
return 1;
bool[] prime = new bool[n + 1];
bool[] primesquare = new bool[(n * n) + 1];
// for storing primes upto n
int[] a = new int[n];
// Calling SieveOfEratosthenes to
// store prime factors of n and to
// store square of prime factors of n
SieveOfEratosthenes(n, prime, primesquare, a);
// ans will contain total number
// of distinct divisors
int ans = 1;
// Loop for counting factors of n
for (int i = 0;; i++) {
// a[i] is not less than cube root n
if (a[i] * a[i] * a[i] > n)
break;
// Calculating power of a[i] in n.
// cnt is power of prime a[i] in n.
int cnt = 1;
// if a[i] is a factor of n
while (n % a[i] == 0) {
n = n / a[i];
// incrementing power
cnt = cnt + 1;
}
// Calculating the number of divisors
// If n = a^p * b^q then total
// divisors of n are (p+1)*(q+1)
ans = ans * cnt;
}
// if a[i] is greater than cube root
// of n
// First case
if (prime[n])
ans = ans * 2;
// Second case
else if (primesquare[n])
ans = ans * 3;
// Third case
else if (n != 1)
ans = ans * 4;
return ans; // Total divisors
}
// Driver Program
public static void Main()
{
Console.Write("Total distinct divisors"
+ " of 100 are : " + countDivisors(100));
}
}
// This code is contributed by parashar.
PHP
<?php
// PHP program to count distinct
// divisors of a given number n
function SieveOfEratosthenes($n, &$prime,
&$primesquare, &$a)
{
// Create a boolean array "prime[0..n]"
// and initialize all entries it as
// true. A value in prime[i] will finally
// be false if i is not a prime, else true.
for ($i = 2; $i <= $n; $i++)
$prime[$i] = true;
// Create a boolean array "primesquare[0..n*n+1]"
// and initialize all entries it as false.
// A value in squareprime[i] will finally be
// true if i is square of prime, else false.
for ($i = 0; $i <= ($n * $n + 1); $i++)
$primesquare[$i] = false;
// 1 is not a prime number
$prime[1] = false;
for ($p = 2; $p * $p <= $n; $p++)
{
// If prime[p] is not changed,
// then it is a prime
if ($prime[$p] == true)
{
// Update all multiples of p
for ($i = $p * 2;
$i <= $n; $i += $p)
$prime[$i] = false;
}
}
$j = 0;
for ($p = 2; $p <= $n; $p++)
{
if ($prime[$p])
{
// Storing primes in an array
$a[$j] = $p;
// Update value in primesquare[p*p],
// if p is prime.
$primesquare[$p * $p] = true;
$j++;
}
}
}
// Function to count divisors
function countDivisors($n)
{
// If number is 1, then it will
// have only 1 as a factor. So,
// total factors will be 1.
if ($n == 1)
return 1;
$prime = array_fill(false, $n + 1, NULL);
$primesquare = array_fill(false,
$n * $n + 1, NULL);
// for storing primes upto n
$a = array_fill(0, $n, NULL);
// Calling SieveOfEratosthenes to
// store prime factors of n and to
// store square of prime factors of n
SieveOfEratosthenes($n, $prime,
$primesquare, $a);
// ans will contain total
// number of distinct divisors
$ans = 1;
// Loop for counting factors of n
for ($i = 0;; $i++)
{
// a[i] is not less than cube root n
if ($a[$i] * $a[$i] * $a[$i] > $n)
break;
// Calculating power of a[i] in n.
$cnt = 1; // cnt is power of
// prime a[i] in n.
while ($n % $a[$i] == 0) // if a[i] is a
// factor of n
{
$n = $n / $a[$i];
$cnt = $cnt + 1; // incrementing power
}
// Calculating the number of divisors
// If n = a^p * b^q then total
// divisors of n are (p+1)*(q+1)
$ans = $ans * $cnt;
}
// if a[i] is greater than
// cube root of n
// First case
if ($prime[$n])
$ans = $ans * 2;
// Second case
else if ($primesquare[$n])
$ans = $ans * 3;
// Third case
else if ($n != 1)
$ans = $ans * 4;
return $ans; // Total divisors
}
// Driver Code
echo "Total distinct divisors of 100 are : ".
countDivisors(100). "\n";
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to count distinct
// divisors of a given number n
function SieveOfEratosthenes(n, prime, primesquare, a)
{
// Create a boolean array "prime[0..n]" and
// initialize all entries it as true. A value
// in prime[i] will finally be false if i is
// Not a prime, else true.
for(let i = 2; i <= n; i++)
prime[i] = true;
// Create a boolean array "primesquare[0..n*n+1]"
// and initialize all entries it as false.
// A value in squareprime[i] will finally
// be true if i is square of prime,
// else false.
for(let i = 0; i < ((n * n) + 1); i++)
primesquare[i] = false;
// 1 is not a prime number
prime[1] = false;
for(let p = 2; p * p <= n; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples of p
for(let i = p * 2; i <= n; i += p)
prime[i] = false;
}
}
let j = 0;
for(let p = 2; p <= n; p++)
{
if (prime[p])
{
// Storing primes in an array
a[j] = p;
// Update value in
// primesquare[p*p],
// if p is prime.
primesquare[p * p] = true;
j++;
}
}
}
// Function to count divisors
function countDivisors(n)
{
// If number is 1, then it will
// have only 1 as a factor. So,
// total factors will be 1.
if (n == 1)
return 1;
let prime = new Array(n + 1);
let primesquare = new Array((n * n) + 1);
// For storing primes upto n
let a = new Array(n);
for(let i = 0; i < n; i++)
{
a[i] = 0;
}
// Calling SieveOfEratosthenes to
// store prime factors of n and to
// store square of prime factors of n
SieveOfEratosthenes(n, prime, primesquare, a);
// ans will contain total number
// of distinct divisors
let ans = 1;
// Loop for counting factors of n
for(let i = 0;; i++)
{
// a[i] is not less than cube root n
if (a[i] * a[i] * a[i] > n)
break;
// Calculating power of a[i] in n.
// cnt is power of prime a[i] in n.
let cnt = 1;
// If a[i] is a factor of n
while (n % a[i] == 0)
{
n = n / a[i];
// Incrementing power
cnt = cnt + 1;
}
// Calculating the number of divisors
// If n = a^p * b^q then total
// divisors of n are (p+1)*(q+1)
ans = ans * cnt;
}
// If a[i] is greater than cube root
// of n
// First case
if (prime[n])
ans = ans * 2;
// Second case
else if (primesquare[n])
ans = ans * 3;
// Third case
else if (n != 1)
ans = ans * 4;
// Total divisors
return ans;
}
// Driver Code
document.write("Total distinct divisors" +
" of 100 are : " + countDivisors(100));
// This code is contributed by avanitrachhadiya2155
</script>
Producción :
Total distinct divisors of 100 are : 9
Complejidad de tiempo: O (n 1/3 )
Complejidad espacial: O(n)
Este artículo es una contribución de Karun Anantharaman . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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