Encuentra números con n-divisores en un rango dado

Dados tres enteros a, b, n. Su tarea es imprimir el número de números entre a y b, incluyéndolos también que tienen n-divisores. Un número se llama n-divisor si tiene un total de n divisores, incluido el 1 y él mismo. 
Ejemplos: 
 

Input  : a = 1, b = 7, n = 2
Output : 4
There are four numbers with 2 divisors in 
range [1, 7]. The numbers are 2, 3, 5, and 7.

Enfoque ingenuo: 
el enfoque ingenuo es verificar todos los números entre a y b, cuántos de ellos son números n-divisor para hacer esto , averigüe el número de cada divisor para cada número . Si es igual a n, entonces es un número n-divisor
. Enfoque eficiente: 
cualquier número se puede escribir en la forma de su descomposición en factores primos, siendo el número x y p1, p2…pm son los números primos que dividen x, por lo que x = p1 e1 * p2 e2 ….pm em donde e1, e2…em son los exponentes de los números primos p1, p2….pm. Entonces el número de divisores de x será (e1+1)*(e2+1)…*(em+1). 
Ahora, la segunda observación es para números primos mayores que sqrt(x) su exponente no puede exceder 1. Probemos esto por contradicción, supongamos que hay un número primo P mayor que sqrt(x) y su exponente E en factorización prima de x es mayor que uno (E >= 2) entonces P^E sqrt(x) entonces P^E > (sqrt(x)) E y E >= 2 entonces P E siempre será mayor que x 
La tercera observación es que el número de números primos es mayor que sqrt(x) en la descomposición en factores primos de x siempre será menor que igual a 1. Esto también se puede probar de manera similar por contradicción como arriba.
Ahora, para resolver este problema, 
paso 1: aplique la criba de eratóstenes y calcule los números primos hasta sqrt (b).
Paso 2:Recorra cada número de a a b y calcule los exponentes de cada número primo en ese número dividiendo repetidamente ese número por el número primo y use la fórmula número de divisores (x) = (e1+1)*(e2+1)….(em +1).
Paso 3: Si después de dividir por todos los números primos menores que igual a la raíz cuadrada de ese número si el número > 1 esto significa que hay un número primo mayor que su raíz cuadrada que divide y su exponente siempre será uno como se demostró anteriormente. 
 

C++

// C++ program to count numbers with n divisors
#include<bits/stdc++.h>
using namespace std;
 
// applying sieve of eratosthenes
void sieve(bool primes[], int x)
{
    primes[1] = false;
 
    // if a number is prime mark all its multiples
    // as non prime
    for (int i=2; i*i <= x; i++)
    {
        if (primes[i] == true)
        {
            for (int j=2; j*j <= x; j++)
                primes[i*j] = false;
        }
    }
}
 
// function that returns numbers of number that have
// n divisors in range from a to b. x is sqrt(b) + 1.
int nDivisors(bool primes[], int x, int a, int b, int n)
{
    // result holds number of numbers having n divisors
    int result = 0;
 
    // vector to hold all the prime numbers between 1
    // ans sqrt(b)
    vector <int> v;
    for (int i = 2; i <= x; i++)
        if (primes[i] == true)
            v.push_back (i);
 
    // Traversing all numbers in given range
    for (int i=a; i<=b; i++)
    {
        // initialising temp as i
        int temp = i;
 
        // total holds the number of divisors of i
        int total = 1;
        int j = 0;
 
        // we need to use that prime numbers that
        // are less than equal to sqrt(temp)
        for (int k = v[j]; k*k <= temp; k = v[++j])
        {
            // holds the exponent of k in prime
            // factorization of i
            int count = 0;
 
            // repeatedly divide temp by k till it is
            // divisible and accordingly increase count
            while (temp%k == 0)
            {
                count++;
                temp = temp/k;
            }
 
            // using the formula  no.of divisors =
            // (e1+1)*(e2+1)....
            total = total*(count+1);
        }
 
        // if temp is not equal to 1 then there is
        // prime number in prime factorization of i
        // greater than sqrt(i)
        if (temp != 1)
            total = total*2;
 
        // if i is a ndvisor number increase result
        if (total == n)
            result++;
    }
    return result;
}
 
// Returns count of numbers in [a..b] having
// n divisors.
int countNDivisors(int a, int b, int n)
{
    int x = sqrt(b) + 1;
 
    // primes[i] = true if i is a prime number
    bool primes[x];
 
    // initialising each number as prime
    memset(primes, true, sizeof(primes));
    sieve(primes, x);
 
    return nDivisors(primes, x, a, b, n);
}
 
// driver code
int main()
{
    int a = 1, b = 7, n = 2;
    cout << countNDivisors(a, b, n);
    return 0;
}

Java

// Java program to count numbers with n divisors
import java.util.*;
 
class GFG{
// applying sieve of eratosthenes
static void sieve(boolean[] primes, int x)
{
    primes[1] = true;
 
    // if a number is prime mark all its multiples
    // as non prime
    for (int i=2; i*i <= x; i++)
    {
        if (primes[i] == false)
        {
            for (int j=2; j*i <= x; j++)
                primes[i*j] = true;
        }
    }
}
 
// function that returns numbers of number that have
// n divisors in range from a to b. x is sqrt(b) + 1.
static int nDivisors(boolean[] primes, int x, int a, int b, int n)
{
    // result holds number of numbers having n divisors
    int result = 0;
 
    // vector to hold all the prime numbers between 1
    // ans sqrt(b)
    ArrayList<Integer> v=new ArrayList<Integer>();
    for (int i = 2; i <= x; i++)
        if (primes[i] == false)
            v.add(i);
     
    // Traversing all numbers in given range
    for (int i=a; i<=b; i++)
    {
        // initialising temp as i
        int temp = i;
 
        // total holds the number of divisors of i
        int total = 1;
        int j = 0;
 
        // we need to use that prime numbers that
        // are less than equal to sqrt(temp)
        for (int k = v.get(j); k*k <= temp; k = v.get(++j))
        {
            // holds the exponent of k in prime
            // factorization of i
            int count = 0;
 
            // repeatedly divide temp by k till it is
            // divisible and accordingly increase count
            while (temp%k == 0)
            {
                count++;
                temp = temp/k;
            }
 
            // using the formula no.of divisors =
            // (e1+1)*(e2+1)....
            total = total*(count+1);
             
        }
 
        // if temp is not equal to 1 then there is
        // prime number in prime factorization of i
        // greater than sqrt(i)
        if (temp != 1)
            total = total*2;
 
        // if i is a ndvisor number increase result
        if (total == n)
            result++;
    }
    return result;
}
 
// Returns count of numbers in [a..b] having
// n divisors.
static int countNDivisors(int a, int b, int n)
{
    int x = (int)Math.sqrt(b) + 1;
 
    // primes[i] = true if i is a prime number
    boolean[] primes=new boolean[x+1];
 
    // initialising each number as prime
    sieve(primes, x);
 
    return nDivisors(primes, x, a, b, n);
}
 
// driver code
public static void main(String[] args)
{
    int a = 1, b = 7, n = 2;
    System.out.println(countNDivisors(a, b, n));
  
}
}
// This code is contributed by mits

Python3

# Python3 program to count numbers
# with n divisors
import math;
 
# applying sieve of eratosthenes
def sieve(primes, x):
    primes[1] = False;
     
    # if a number is prime mark all
    # its multiples as non prime
    i = 2;
    while (i * i <= x):
        if (primes[i] == True):
            j = 2;
            while (j * i <= x):
                primes[i * j] = False;
                j += 1;
        i += 1;
 
# function that returns numbers of number
# that have n divisors in range from a to b.
# x is sqrt(b) + 1.
def nDivisors(primes, x, a, b, n):
     
    # result holds number of numbers
    # having n divisors
    result = 0;
 
    # vector to hold all the prime
    # numbers between 1 and sqrt(b)
    v = [];
    for i in range(2, x + 1):
        if (primes[i]):
            v.append(i);
 
    # Traversing all numbers in given range
    for i in range(a, b + 1):
         
        # initialising temp as i
        temp = i;
 
        # total holds the number of
        # divisors of i
        total = 1;
        j = 0;
 
        # we need to use that prime numbers that
        # are less than equal to sqrt(temp)
        k = v[j];
        while (k * k <= temp):
             
            # holds the exponent of k in prime
            # factorization of i
            count = 0;
 
            # repeatedly divide temp by k till it is
            # divisible and accordingly increase count
            while (temp % k == 0):
                count += 1;
                temp = int(temp / k);
 
            # using the formula no.of divisors =
            # (e1+1)*(e2+1)....
            total = total * (count + 1);
            j += 1;
            k = v[j];
 
        # if temp is not equal to 1 then there is
        # prime number in prime factorization of i
        # greater than sqrt(i)
        if (temp != 1):
            total = total * 2;
 
        # if i is a ndivisor number
        # increase result
        if (total == n):
            result += 1;
    return result;
 
# Returns count of numbers in [a..b]
# having n divisors.
def countNDivisors(a, b, n):
    x = int(math.sqrt(b) + 1);
 
    # primes[i] = true if i is a prime number
    # initialising each number as prime
    primes = [True] * (x + 1);
    sieve(primes, x);
 
    return nDivisors(primes, x, a, b, n);
 
# Driver code
a = 1;
b = 7;
n = 2;
print(countNDivisors(a, b, n));
 
# This code is contributed by mits

C#

// C# program to count numbers with n divisors
using System.Collections;
using System;
class GFG{
// applying sieve of eratosthenes
static void sieve(bool[] primes, int x)
{
    primes[1] = true;
 
    // if a number is prime mark all its multiples
    // as non prime
    for (int i=2; i*i <= x; i++)
    {
        if (primes[i] == false)
        {
            for (int j=2; j*i <= x; j++)
                primes[i*j] = true;
        }
    }
}
 
// function that returns numbers of number that have
// n divisors in range from a to b. x is sqrt(b) + 1.
static int nDivisors(bool[] primes, int x, int a, int b, int n)
{
    // result holds number of numbers having n divisors
    int result = 0;
 
    // vector to hold all the prime numbers between 1
    // ans sqrt(b)
    ArrayList v=new ArrayList();
    for (int i = 2; i <= x; i++)
        if (primes[i] == false)
            v.Add(i);
     
    // Traversing all numbers in given range
    for (int i=a; i<=b; i++)
    {
        // initialising temp as i
        int temp = i;
 
        // total holds the number of divisors of i
        int total = 1;
        int j = 0;
 
        // we need to use that prime numbers that
        // are less than equal to sqrt(temp)
        for (int k = (int)v[j]; k*k <= temp; k = (int)v[++j])
        {
            // holds the exponent of k in prime
            // factorization of i
            int count = 0;
 
            // repeatedly divide temp by k till it is
            // divisible and accordingly increase count
            while (temp%k == 0)
            {
                count++;
                temp = temp/k;
            }
 
            // using the formula no.of divisors =
            // (e1+1)*(e2+1)....
            total = total*(count+1);
             
        }
 
        // if temp is not equal to 1 then there is
        // prime number in prime factorization of i
        // greater than sqrt(i)
        if (temp != 1)
            total = total*2;
 
        // if i is a ndivisor number increase result
        if (total == n)
            result++;
    }
    return result;
}
 
// Returns count of numbers in [a..b] having
// n divisors.
static int countNDivisors(int a, int b, int n)
{
    int x = (int)Math.Sqrt(b) + 1;
 
    // primes[i] = true if i is a prime number
    bool[] primes=new bool[x+1];
 
    // initialising each number as prime
    sieve(primes, x);
 
    return nDivisors(primes, x, a, b, n);
}
 
// driver code
public static void Main()
{
    int a = 1, b = 7, n = 2;
    Console.WriteLine(countNDivisors(a, b, n));
  
}
}
// This code is contributed by mits

PHP

<?php
// PHP program to count numbers with n divisors
 
// applying sieve of eratosthenes
function sieve(&$primes, $x)
{
    $primes[1] = false;
 
    // if a number is prime mark all
    // its multiples as non prime
    for ($i = 2; $i * $i <= $x; $i++)
    {
        if ($primes[$i] == true)
        {
            for ($j = 2; $j * $i <= $x; $j++)
                $primes[$i * $j] = false;
        }
    }
}
 
// function that returns numbers of number
// that have n divisors in range from a to
// b. x is sqrt(b) + 1.
function nDivisors($primes, $x, $a, $b, $n)
{
    // result holds number of numbers
    // having n divisors
    $result = 0;
 
    // vector to hold all the prime numbers
    // between 1 ans sqrt(b)
    $v = array();
    for ($i = 2; $i <= $x; $i++)
        if ($primes[$i] == true)
            array_push($v, $i);
 
    // Traversing all numbers in given range
    for ($i = $a; $i <= $b; $i++)
    {
        // initialising temp as i
        $temp = $i;
 
        // total holds the number of
        // divisors of i
        $total = 1;
        $j = 0;
 
        // we need to use that prime numbers that
        // are less than equal to sqrt(temp)
        for ($k = $v[$j];
             $k * $k <= $temp; $k = $v[++$j])
        {
            // holds the exponent of k in
            // prime factorization of i
            $count = 0;
 
            // repeatedly divide temp by k till
            // it is divisible and accordingly
            // increase count
            while ($temp % $k == 0)
            {
                $count++;
                $temp = (int)($temp / $k);
            }
 
            // using the formula no.of divisors =
            // (e1+1)*(e2+1)....
            $total = $total * ($count + 1);
        }
 
        // if temp is not equal to 1 then there is
        // prime number in prime factorization of i
        // greater than sqrt(i)
        if ($temp != 1)
            $total = $total * 2;
 
        // if i is a n divisor number increase result
        if ($total == $n)
            $result++;
    }
    return $result;
}
 
// Returns count of numbers in [a..b]
// having n divisors.
function countNDivisors($a, $b, $n)
{
    $x = (int)(sqrt($b) + 1);
 
    // primes[i] = true if i is a prime number
    // initialising each number as prime
    $primes = array_fill(0, $x + 1, true);
    sieve($primes, $x);
 
    return nDivisors($primes, $x, $a, $b, $n);
}
 
// Driver code
$a = 1;
$b = 7;
$n = 2;
print(countNDivisors($a, $b, $n));
 
// This code is contributed by mits
?>

Javascript

<script>
 
// Javascript program to count numbers with n divisors
 
// applying sieve of eratosthenes
function sieve(primes, x)
{
    primes[1] = true;
 
    // if a number is prime mark all its multiples
    // as non prime
    for (var i=2; i*i <= x; i++)
    {
        if (primes[i] == false)
        {
            for (var j=2; j*i <= x; j++)
                primes[i*j] = true;
        }
    }
}
 
// function that returns numbers of number that have
// n divisors in range from a to b. x is sqrt(b) + 1.
function nDivisors(primes, x,  a, b, n)
{
    // result holds number of numbers having n divisors
    var result = 0;
 
    // vector to hold all the prime numbers between 1
    // ans sqrt(b)
    var v = [];
    for (var i = 2; i <= x; i++)
        if (primes[i] == false)
            v.push(i);
     
    // Traversing all numbers in given range
    for (var i=a; i<=b; i++)
    {
        // initialising temp as i
        var temp = i;
 
        // total holds the number of divisors of i
        var total = 1;
        var j = 0;
 
        // we need to use that prime numbers that
        // are less than equal to sqrt(temp)
        for (var k = v[j]; k*k <= temp; k = v[++j])
        {
            // holds the exponent of k in prime
            // factorization of i
            var count = 0;
 
            // repeatedly divide temp by k till it is
            // divisible and accordingly increase count
            while (temp%k == 0)
            {
                count++;
                temp = parseInt(temp/k);
            }
 
            // using the formula no.of divisors =
            // (e1+1)*(e2+1)....
            total = total*(count+1);
             
        }
 
        // if temp is not equal to 1 then there is
        // prime number in prime factorization of i
        // greater than sqrt(i)
        if (temp != 1)
            total = total*2;
 
        // if i is a ndivisor number increase result
        if (total == n)
            result++;
    }
    return result;
}
 
// Returns count of numbers in [a..b] having
// n divisors.
function countNDivisors(a, b, n)
{
    var x = parseInt(Math.sqrt(b)) + 1;
 
    // primes[i] = true if i is a prime number
    var primes = Array(x+1).fill(false);
 
    // initialising each number as prime
    sieve(primes, x);
 
    return nDivisors(primes, x, a, b, n);
}
 
// driver code
var a = 1, b = 7, n = 2;
document.write(countNDivisors(a, b, n));
 
// This code is contributed by rutvik_56.
</script>

Producción: 
 

4

Complejidad temporal: O(n) 
Espacio auxiliar: O(n)
 

 

Este artículo es una contribución de Aarti_Rathi y Ayush Jha . 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *