Dados dos números enteros N y K , la tarea es contar todos los números < N que tienen el mismo número de divisores positivos que K .
Ejemplos:
Entrada: n = 10, k = 5
Salida: 3
2, 3 y 7 son los únicos números < 10 que tienen 2 divisores (igual al número de divisores de 5)
Entrada: n = 500, k = 6
Salida: 148
Acercarse:
- Calcule el número de divisores de cada número < N y almacene el resultado en una array donde arr[i] contiene el número de divisores de i .
- Recorra arr[] , si arr[i] = arr[K] entonces actualice count = count + 1 .
- Imprime el valor de conteo al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of the
// divisors of a number
int countDivisors(int n)
{
// Count the number of
// 2s that divide n
int x = 0, ans = 1;
while (n % 2 == 0) {
x++;
n = n / 2;
}
ans = ans * (x + 1);
// n must be odd at this point.
// So we can skip one element
for (int i = 3; i <= sqrt(n); i = i + 2) {
// While i divides n
x = 0;
while (n % i == 0) {
x++;
n = n / i;
}
ans = ans * (x + 1);
}
// This condition is to
// handle the case when
// n is a prime number > 2
if (n > 2)
ans = ans * 2;
return ans;
}
int getTotalCount(int n, int k)
{
int k_count = countDivisors(k);
// Count the total elements
// that have divisors exactly equal
// to as that of k's
int count = 0;
for (int i = 1; i < n; i++)
if (k_count == countDivisors(i))
count++;
// Exclude k from the result if it
// is smaller than n.
if (k < n)
count = count - 1;
return count;
}
// Driver code
int main()
{
int n = 500, k = 6;
cout << getTotalCount(n, k);
return 0;
}
Java
// Java implementation of the approach
public class GFG{
// Function to return the count of the
// divisors of a number
static int countDivisors(int n)
{
// Count the number of
// 2s that divide n
int x = 0, ans = 1;
while (n % 2 == 0) {
x++;
n = n / 2;
}
ans = ans * (x + 1);
// n must be odd at this point.
// So we can skip one element
for (int i = 3; i <= Math.sqrt(n); i = i + 2) {
// While i divides n
x = 0;
while (n % i == 0) {
x++;
n = n / i;
}
ans = ans * (x + 1);
}
// This condition is to
// handle the case when
// n is a prime number > 2
if (n > 2)
ans = ans * 2;
return ans;
}
static int getTotalCount(int n, int k)
{
int k_count = countDivisors(k);
// Count the total elements
// that have divisors exactly equal
// to as that of k's
int count = 0;
for (int i = 1; i < n; i++)
if (k_count == countDivisors(i))
count++;
// Exclude k from the result if it
// is smaller than n.
if (k < n)
count = count - 1;
return count;
}
// Driver code
public static void main(String []args)
{
int n = 500, k = 6;
System.out.println(getTotalCount(n, k));
}
// This code is contributed by Ryuga
}
Python3
# Python3 implementation of the approach # Function to return the count of # the divisors of a number def countDivisors(n): # Count the number of 2s that divide n x, ans = 0, 1 while (n % 2 == 0): x += 1 n = n / 2 ans = ans * (x + 1) # n must be odd at this point. # So we can skip one element for i in range(3, int(n ** 1 / 2) + 1, 2): # While i divides n x = 0 while (n % i == 0): x += 1 n = n / i ans = ans * (x + 1) # This condition is to handle the # case when n is a prime number > 2 if (n > 2): ans = ans * 2 return ans def getTotalCount(n, k): k_count = countDivisors(k) # Count the total elements that # have divisors exactly equal # to as that of k's count = 0 for i in range(1, n): if (k_count == countDivisors(i)): count += 1 # Exclude k from the result if it # is smaller than n. if (k < n): count = count - 1 return count # Driver code if __name__ == '__main__': n, k = 500, 6 print(getTotalCount(n, k)) # This code is contributed # by 29AjayKumar
C#
// C# implementation of the approach
using System;
public class GFG{
// Function to return the count of the
// divisors of a number
static int countDivisors(int n)
{
// Count the number of
// 2s that divide n
int x = 0, ans = 1;
while (n % 2 == 0) {
x++;
n = n / 2;
}
ans = ans * (x + 1);
// n must be odd at this point.
// So we can skip one element
for (int i = 3; i <= Math.Sqrt(n); i = i + 2) {
// While i divides n
x = 0;
while (n % i == 0) {
x++;
n = n / i;
}
ans = ans * (x + 1);
}
// This condition is to
// handle the case when
// n is a prime number > 2
if (n > 2)
ans = ans * 2;
return ans;
}
static int getTotalCount(int n, int k)
{
int k_count = countDivisors(k);
// Count the total elements
// that have divisors exactly equal
// to as that of k's
int count = 0;
for (int i = 1; i < n; i++)
if (k_count == countDivisors(i))
count++;
// Exclude k from the result if it
// is smaller than n.
if (k < n)
count = count - 1;
return count;
}
// Driver code
public static void Main()
{
int n = 500, k = 6;
Console.WriteLine(getTotalCount(n, k));
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
//PHP implementation of the approach
// Function to return the count of the
// divisors of a number
function countDivisors($n)
{
// Count the number of
// 2s that divide n
$x = 0;
$ans = 1;
while ($n % 2 == 0) {
$x++;
$n = $n / 2;
}
$ans = $ans * ($x + 1);
// n must be odd at this point.
// So we can skip one element
for ($i = 3; $i <= sqrt($n); $i = $i + 2) {
// While i divides n
$x = 0;
while ($n % $i == 0) {
$x++;
$n = $n / $i;
}
$ans = $ans * ($x + 1);
}
// This condition is to
// handle the case when
// n is a prime number > 2
if ($n > 2)
$ans = $ans * 2;
return $ans;
}
function getTotalCount($n, $k)
{
$k_count = countDivisors($k);
// Count the total elements
// that have divisors exactly equal
// to as that of k's
$count = 0;
for ($i = 1; $i < $n; $i++)
if ($k_count == countDivisors($i))
$count++;
// Exclude k from the result if it
// is smaller than n.
if ($k < $n)
$count = $count - 1;
return $count;
}
// Driver code
$n = 500;
$k = 6;
echo getTotalCount($n, $k);
#This code is contributed by Sachin..
?>
Javascript
<script>
//Javascript implementation of the approach
// Function to return the count of the
// divisors of a number
function countDivisors(n)
{
// Count the number of
// 2s that divide n
var x = 0, ans = 1;
while (n % 2 == 0) {
x++;
n = n / 2;
}
ans = ans * (x + 1);
// n must be odd at this point.
// So we can skip one element
for (var i = 3; i <= Math.sqrt(n); i = i + 2)
{
// While i divides n
x = 0;
while (n % i == 0) {
x++;
n = n / i;
}
ans = ans * (x + 1);
}
// This condition is to
// handle the case when
// n is a prime number > 2
if (n > 2)
ans = ans * 2;
return ans;
}
function getTotalCount( n, k)
{
var k_count = countDivisors(k);
// Count the total elements
// that have divisors exactly equal
// to as that of k's
var count = 0;
for (var i = 1; i < n; i++)
if (k_count == countDivisors(i))
count++;
// Exclude k from the result if it
// is smaller than n.
if (k < n)
count = count - 1;
return count;
}
var n = 500, k = 6;
document.write(getTotalCount(n, k));
// This code is contributed by SoumikMondal
</script>
Producción:
148
Complejidad de tiempo: O(nsqrtn*logn)
Espacio Auxiliar: O(1)
Optimización:
la solución anterior se puede optimizar utilizando la técnica Sieve . Consulte Contar el número de enteros menores o iguales a N que tiene exactamente 9 divisores para obtener más detalles.