Kleinste ganze Zahl, die n oder mehr Faktoren hat
Gegeben n, finde die kleinste ganze Zahl, die n oder mehr Faktoren hat. Es kann davon ausgegangen werden, dass das Ergebnis kleiner als 1000001 ist.
Beispiele:
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.
Es gibt viele Methoden, um die Anzahl der Faktoren zu berechnen, aber die effizienteste finden Sie hier .
Einfacher Ansatz: Ein einfacher Ansatz besteht darin, eine Schleife auszuführen, um die Faktoren einer Zahl herauszufinden. Eine Möglichkeit, die Faktoren einer Zahl in O(x) herauszufinden, besteht darin, eine Schleife von 1 bis x zu durchlaufen und alle Zahlen zu sehen, die x teilen.
Zeitkomplexität: O(x) für jede Zahl x, die wir versuchen, bis wir die Antwort finden oder das Limit erreichen.
Effizienter Ansatz: Wir können Faktoren in sqrt(x) für jede Iteration herausfinden .
Zeitkomplexität: O(sqrt(x)) für jede Zahl x, die wir versuchen, bis wir die Antwort finden oder das Limit erreichen.
Der beste Ansatz besteht darin, jede Zahl zu durchlaufen und die Anzahl der Faktoren zu berechnen . Überprüfen Sie dann, ob die Anzahl gleich oder größer als n ist, dann erhalten wir unsere gewünschte kleinste ganze Zahl mit n oder mehr Faktoren.
Unten ist die Implementierung des obigen Ansatzes:
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 prvar 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>
Ausgabe:
6
Zeitkomplexität: O(log(max(number))) für jede Berechnungszahl, die wir überprüfen, bevor wir die Antwort erhalten.