Dado n, encuentre el entero más pequeño que tenga n factores o más. Se puede suponer que el resultado es menor que 1000001.
Ejemplos:
Input : n = 3 Output : 4 Explanation: 4 has factors 1, 2 and 4. Input : n = 2 Output : 2 Explanation: 2 has one factor 1 and 2.
Hay muchos métodos para calcular el número de factores, pero el eficiente se puede encontrar aquí
. Enfoque simple: un enfoque simple será ejecutar un ciclo para encontrar los factores de un número. Uno para encontrar los factores de un número en O(x) es ejecutar un bucle de 1 a x y ver todos los números que dividen x.
Complejidad Temporal: O(x) por cada número x que intentamos hasta encontrar la respuesta o llegar al límite.
Enfoque eficiente: podemos encontrar factores en sqrt (x) para cada iteración.
Complejidad temporal: O(sqrt(x)) por cada número x que intentamos hasta encontrar la respuesta o llegar al límite.
El mejor enfoque será recorrer cada número y calcular el número de factores . Luego verifique si el conteo es igual o mayor que n, luego obtenemos nuestro entero más pequeño deseado con n o más factores.
A continuación se muestra la implementación del enfoque anterior:
C++
// c++ program to print the smallest // integer with n factors or more #include <bits/stdc++.h> using namespace std; const int MAX = 1000001; // array to store prime factors int factor[MAX] = { 0 }; // function to generate all prime factors // of numbers from 1 to 10^6 void generatePrimeFactors() { factor[1] = 1; // Initializes all the positions // with their value. for (int i = 2; i < MAX; i++) factor[i] = i; // Initializes all multiples of 2 with 2 for (int i = 4; i < MAX; i += 2) factor[i] = 2; // A modified version of Sieve of // Eratosthenes to store the smallest // prime factor that divides every number. for (int i = 3; i * i < MAX; i++) { // check if it has no prime factor. if (factor[i] == i) { // Initializes of j starting from i*i for (int j = i * i; j < MAX; j += i) { // if it has no prime factor // before, then stores the // smallest prime divisor if (factor[j] == j) factor[j] = i; } } } } // function to calculate number of factors int calculateNoOFactors(int n) { if (n == 1) return 1; int ans = 1; // stores the smallest prime number // that divides n int dup = factor[n]; // stores the count of number of times // a prime number divides n. int c = 1; // reduces to the next number after prime // factorization of n int j = n / factor[n]; // false when prime factorization is done while (j != 1) { // if the same prime number is dividing n, // then we increase the count if (factor[j] == dup) c += 1; /* if its a new prime factor that is factorizing n, then we again set c=1 and change dup to the new prime factor, and apply the formula explained above. */ else { dup = factor[j]; ans = ans * (c + 1); c = 1; } // prime factorizes a number j = j / factor[j]; } // for the last prime factor ans = ans * (c + 1); return ans; } // function to find the smallest integer // with n factors or more. int smallest(int n) { for (int i = 1;; i++) // check if no of factors is more // than n or not if (calculateNoOFactors(i) >= n) return i; } // Driver program to test above function int main() { // generate prime factors of number // upto 10^6 generatePrimeFactors(); int n = 4; cout << smallest(n); return 0; }
Java
// Java program to print the smallest // integer with n factors or more import java.util.*; import java.lang.*; public class GfG{ private static final int MAX = 1000001; // array to store prime factors private static final int[] factor = new int [MAX]; // function to generate all prime factors // of numbers from 1 to 10^6 public static void generatePrimeFactors() { factor[1] = 1; // Initializes all the positions // with their value. for (int i = 2; i < MAX; i++) factor[i] = i; // Initializes all multiples of 2 with 2 for (int i = 4; i < MAX; i += 2) factor[i] = 2; // A modified version of Sieve of // Eratosthenes to store the smallest // prime factor that divides every number. for (int i = 3; i * i < MAX; i++) { // check if it has no prime factor. if (factor[i] == i) { // Initializes of j starting from i*i for (int j = i * i; j < MAX; j += i) { // if it has no prime factor // before, then stores the // smallest prime divisor if (factor[j] == j) factor[j] = i; } } } } // function to calculate number of factors public static int calculateNoOFactors(int n) { if (n == 1) return 1; int ans = 1; // stores the smallest prime number // that divides n int dup = factor[n]; // stores the count of number of times // a prime number divides n. int c = 1; // reduces to the next number after prime // factorization of n int j = n / factor[n]; // false when prime factorization is done while (j != 1) { // if the same prime number is dividing n, // then we increase the count if (factor[j] == dup) c += 1; /* if its a new prime factor that is factorizing n, then we again set c=1 and change dup to the new prime factor, and apply the formula explained above. */ else { dup = factor[j]; ans = ans * (c + 1); c = 1; } // prime factorizes a number j = j / factor[j]; } // for the last prime factor ans = ans * (c + 1); return ans; } // function to find the smallest integer // with n factors or more. public static int smallest(int n) { for (int i = 1;; i++) // check if no of factors is more // than n or not if (calculateNoOFactors(i) >= n) return i; } // driver function public static void main(String args[]) { // generate prime factors of number // upto 10^6 generatePrimeFactors(); int n = 4; System.out.println(smallest(n)); } } /* This code is contributed by Sagar Shukla */
Python3
# Python3 program to print the # smallest integer with n # factors or more MAX = 100001; # array to store # prime factors factor = [0] * MAX; # function to generate all # prime factors of numbers # from 1 to 10^6 def generatePrimeFactors(): factor[1] = 1; # Initializes all the # positions with their value. for i in range(2, MAX): factor[i] = i; # Initializes all # multiples of 2 with 2 i = 4 while(i < MAX): factor[i] = 2; i += 2; # A modified version of # Sieve of Eratosthenes # to store the smallest # prime factor that # divides every number. i = 3; while(i * i < MAX): # check if it has # no prime factor. if (factor[i] == i): # Initializes of j # starting from i*i j = i * i; while(j < MAX): # if it has no prime factor # before, then stores the # smallest prime divisor if (factor[j] == j): factor[j] = i; j += i; i += 1; # function to calculate # number of factors def calculateNoOFactors(n): if (n == 1): return 1; ans = 1; # stores the smallest prime # number that divides n dup = factor[n]; # stores the count of # number of times a # prime number divides n. c = 1; # reduces to the next # number after prime # factorization of n j = int(n / factor[n]); # false when prime # factorization is done while (j != 1): # if the same prime number # is dividing n, then we # increase the count if (factor[j] == dup): c += 1; # if its a new prime factor # that is factorizing n, then # we again set c=1 and change # dup to the new prime factor, # and apply the formula # explained above. else: dup = factor[j]; ans = ans * (c + 1); c = 1; # prime factorizes a number j = int(j / factor[j]); # for the last prime factor ans = ans * (c + 1); return ans; # function to find the # smallest integer with # n factors or more. def smallest(n): i = 1; while(True): # check if no of # factors is more # than n or not if (calculateNoOFactors(i) >= n): return i; i += 1; # Driver Code # generate prime factors # of number upto 10^6 generatePrimeFactors(); n = 4; print(smallest(n)); # This code is contributed by mits
C#
// C# program to print the smallest // integer with n factors or more using System; class GfG { private static int MAX = 1000001; // array to store prime factors private static int []factor = new int [MAX]; // function to generate all prime // factorsof numbers from 1 to 10^6 public static void generatePrimeFactors() { factor[1] = 1; // Initializes all the positions // with their value. for (int i = 2; i < MAX; i++) factor[i] = i; // Initializes all multiples of 2 with 2 for (int i = 4; i < MAX; i += 2) factor[i] = 2; // A modified version of Sieve of // Eratosthenes to store the smallest // prime factor that divides every number. for (int i = 3; i * i < MAX; i++) { // check if it has no prime factor. if (factor[i] == i) { // Initializes of j starting from i*i for (int j = i * i; j < MAX; j += i) { // if it has no prime factor // before, then stores the // smallest prime divisor if (factor[j] == j) factor[j] = i; } } } } // function to calculate number of factors public static int calculateNoOFactors(int n) { if (n == 1) return 1; int ans = 1; // stores the smallest prime number // that divides n int dup = factor[n]; // stores the count of number of times // a prime number divides n. int c = 1; // reduces to the next number after prime // factorization of n int j = n / factor[n]; // false when prime factorization is done while (j != 1) { // if the same prime number is dividing n, // then we increase the count if (factor[j] == dup) c += 1; // if its a new prime factor that is // factorizing n, then we again set c=1 // and change dup to the new prime factor, // and apply the formula explained above. else { dup = factor[j]; ans = ans * (c + 1); c = 1; } // prime factorizes a number j = j / factor[j]; } // for the last prime factor ans = ans * (c + 1); return ans; } // function to find the smallest integer // with n factors or more. public static int smallest(int n) { for (int i = 1; ; i++) // check if no of factors is more // than n or not if (calculateNoOFactors(i) >= n) return i; } // Driver Code public static void Main() { // generate prime factors of // number upto 10^6 generatePrimeFactors(); int n = 4; Console.Write(smallest(n)); } } // This code is contributed by Nitin Mittal.
PHP
<?php // PHP program to print the // smallest integer with n // factors or more $MAX = 100001; // array to store // prime factors $factor = array_fill(0, $MAX, 0); // function to generate all // prime factors of numbers // from 1 to 10^6 function generatePrimeFactors() { global $MAX; global $factor; $factor[1] = 1; // Initializes all the // positions with their value. for ($i = 2; $i < $MAX; $i++) $factor[$i] = $i; // Initializes all // multiples of 2 with 2 for ($i = 4; $i < $MAX; $i += 2) $factor[$i] = 2; // A modified version of // Sieve of Eratosthenes // to store the smallest // prime factor that // divides every number. for ($i = 3; $i * $i < $MAX; $i++) { // check if it has // no prime factor. if ($factor[$i] == $i) { // Initializes of j // starting from i*i for ($j = $i * $i; $j < $MAX; $j += $i) { // if it has no prime factor // before, then stores the // smallest prime divisor if ($factor[$j] == $j) $factor[$j] = $i; } } } } // function to calculate // number of factors function calculateNoOFactors($n) { global $factor; if ($n == 1) return 1; $ans = 1; // stores the smallest prime // number that divides n $dup = $factor[$n]; // stores the count of // number of times a // prime number divides n. $c = 1; // reduces to the next // number after prime // factorization of n $j = (int)($n / $factor[$n]); // false when prime // factorization is done while ($j != 1) { // if the same prime number // is dividing n, then we // increase the count if ($factor[$j] == $dup) $c += 1; /* if its a new prime factor that is factorizing n, then we again set c=1 and change dup to the new prime factor, and apply the formula explained above. */ else { $dup = $factor[$j]; $ans = $ans * ($c + 1); $c = 1; } // prime factorizes a number $j = (int)($j / $factor[$j]); } // for the last prime factor $ans = $ans * ($c + 1); return $ans; } // function to find the // smallest integer with // n factors or more. function smallest($n) { for ($i = 1;; $i++) // check if no of // factors is more // than n or not if (calculateNoOFactors($i) >= $n) return $i; } // Driver Code // generate prime factors // of number upto 10^6 generatePrimeFactors(); $n = 4; echo smallest($n); // This code is contributed by mits ?>
Javascript
<script> // javascript program to print the smallest // integer with n factors or more var MAX = 1000001; // array to store prime factors var factor = Array(MAX).fill(0); // function to generate all prime factors // of numbers from 1 to 10^6 function generatePrimeFactors() { factor[1] = 1; // Initializes all the positions // with their value. for (i = 2; i < MAX; i++) factor[i] = i; // Initializes all multiples of 2 with 2 for (i = 4; i < MAX; i += 2) factor[i] = 2; // A modified version of Sieve of // Eratosthenes to store the smallest // prime factor that divides every number. for (i = 3; i * i < MAX; i++) { // check if it has no prime factor. if (factor[i] == i) { // Initializes of j starting from i*i for (j = i * i; j < MAX; j += i) { // if it has no prime factor // before, then stores the // smallest prime divisor if (factor[j] == j) factor[j] = i; } } } } // function to calculate number of factors function calculateNoOFactors(n) { if (n == 1) return 1; var ans = 1; // stores the smallest prime number // that divides n var dup = factor[n]; // stores the count of number of times // a prime number divides n. var c = 1; // reduces to the next number after prime // factorization of n var j = n / factor[n]; // false when prime factorization is done while (j != 1) { // if the same prime number is dividing n, // then we increase the count if (factor[j] == dup) c += 1; /* * if its a new prime factor that is factorizing n, then we again set c=1 and * change dup to the new prime factor, and apply the formula explained above. */ else { dup = factor[j]; ans = ans * (c + 1); c = 1; } // prime factorizes a number j = j / factor[j]; } // for the last prime factor ans = ans * (c + 1); return ans; } // function to find the smallest integer // with n factors or more. function smallest(n) { for (i = 1;; i++) // check if no of factors is more // than n or not if (calculateNoOFactors(i) >= n) return i; } // driver function // generate prime factors of number // upto 10^6 generatePrimeFactors(); var n = 4; document.write(smallest(n)); // This code is contributed by todaysgaurav </script>
Producción:
6
Complejidad de tiempo: O(1000001)
Espacio auxiliar: O(1000001), se utiliza el tamaño de esta array
Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.