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