Menor número divisível pelos primeiros n números
Experimente no GfG Practice 
Saída
Dado um número n encontre o menor número igualmente divisível por cada número de 1 a n.
Exemplos:
Input : n = 4 Output : 12 Explanation : 12 is the smallest numbers divisible by all numbers from 1 to 4 Input : n = 10 Output : 2520 Input : n = 20 Output : 232792560
Se você observar atentamente o anos deve ser o MMC dos números de 1 a n .
Para encontrar o MMC de números de 1 a n -
- Inicialize ans = 1.
- Itere sobre todos os números de i = 1 a i = n.
Na i-ésima iteração resposta = LCM (1 2 …… .. i) . Isso pode ser feito facilmente como MMC(1 2….i) = MMC(ans i) .
Assim, na i'ésima iteração, só temos que fazer -
ans = LCM(ans i) = ans * i / gcd(ans i) [Using the below property a*b = gcd(ab) * lcm(ab)]C++
Observação : No código C++, a resposta excede rapidamente o limite inteiro, mesmo o limite longo.
Abaixo está a implementação da lógica.
Java// C++ program to find smallest number evenly divisible by // all numbers 1 to n #includeusing namespace std ; // Function returns the lcm of first n numbers long long lcm ( long long n ) { long long ans = 1 ; for ( long long i = 1 ; i <= n ; i ++ ) ans = ( ans * i ) / ( __gcd ( ans i )); return ans ; } // Driver program to test the above function int main () { long long n = 20 ; cout < < lcm ( n ); return 0 ; } Python// Java program to find the smallest number evenly divisible by // all numbers 1 to n class GFG { static long gcd ( long a long b ) { if ( a % b != 0 ) return gcd ( b a % b ); else return b ; } // Function returns the lcm of first n numbers static long lcm ( long n ) { long ans = 1 ; for ( long i = 1 ; i <= n ; i ++ ) ans = ( ans * i ) / ( gcd ( ans i )); return ans ; } // Driver program to test the above function public static void main ( String [] args ) { long n = 20 ; System . out . println ( lcm ( n )); } }C## Python program to find the smallest number evenly # divisible by all number 1 to n import math # Returns the lcm of first n numbers def lcm ( n ): ans = 1 for i in range ( 1 n + 1 ): ans = int (( ans * i ) / math . gcd ( ans i )) return ans # main n = 20 print ( lcm ( n ))Javascript// C# program to find smallest number // evenly divisible by // all numbers 1 to n using System ; public class GFG { static long gcd ( long a long b ) { if ( a % b != 0 ) return gcd ( b a % b ); else return b ; } // Function returns the lcm of first n numbers static long lcm ( long n ) { long ans = 1 ; for ( long i = 1 ; i <= n ; i ++ ) ans = ( ans * i ) / ( gcd ( ans i )); return ans ; } // Driver program to test the above function static public void Main (){ long n = 20 ; Console . WriteLine ( lcm ( n )); } //This code is contributed by akt_mit }PHP// Javascript program to find the smallest number evenly divisible by // all numbers 1 to n function gcd ( a b ) { if ( a % b != 0 ) return gcd ( b a % b ); else return b ; } // Function returns the lcm of first n numbers function lcm ( n ) { let ans = 1 ; for ( let i = 1 ; i <= n ; i ++ ) ans = ( ans * i ) / ( gcd ( ans i )); return ans ; } // function call let n = 20 ; console . log ( lcm ( n ));
Saída232792560Complexidade de tempo: O (n log2n) já que a complexidade de _gcd(ab) em c++ é log2n e é executado n vezes em um loop.
Espaço Auxiliar: O(1)
A solução acima funciona bem para uma única entrada. Mas se tivermos múltiplas entradas, é uma boa ideia usar o Crivo de Eratóstenes para armazenar todos os fatores primos. Consulte o artigo abaixo para a abordagem baseada em Sieve.Abordagem: [Usando Peneira de Eratóstenes ]
Para resolver o problema de encontrar o menor número divisível pelos primeiros 'n' números de uma forma mais eficiente, podemos usar o Crivo de Eratóstenes para pré-calcular os números primos até 'n'. Então podemos usar esses primos para calcular o mínimo múltiplo comum (MCC) de forma mais eficiente, considerando as potências mais altas de cada primo que são menores ou iguais a 'n'.
Abordagem passo a passo:
- Gere números primos até n: Use a peneira de Eratóstenes para encontrar todos os números primos até 'n'.
- Calcule o MMC usando estes números primos: Para cada primo determine a maior potência desse primo que é menor ou igual a 'n'. Multiplique essas potências mais altas para obter o LCM
Abaixo está a implementação da abordagem acima:
C++ #include #include #include using namespace std ; // Function to generate all prime numbers up to n using the // Sieve of Eratosthenes vector < int > sieve_of_eratosthenes ( int n ) { vector < bool > is_prime ( n + 1 true ); int p = 2 ; while ( p * p <= n ) { if ( is_prime [ p ]) { for ( int i = p * p ; i <= n ; i += p ) { is_prime [ i ] = false ; } } ++ p ; } vector < int > prime_numbers ; for ( int p = 2 ; p <= n ; ++ p ) { if ( is_prime [ p ]) { prime_numbers . push_back ( p ); } } return prime_numbers ; } // Function to find the smallest number divisible by all // numbers from 1 to n long long smallest_multiple ( int n ) { vector < int > primes = sieve_of_eratosthenes ( n ); long long lcm = 1 ; for ( int prime : primes ) { // Calculate the highest power of the prime that is // <= n int power = 1 ; while ( pow ( prime power + 1 ) <= n ) { ++ power ; } lcm *= pow ( prime power ); } return lcm ; } int main () { int n = 20 ; cout < < smallest_multiple ( n ) < < endl ; return 0 ; }
Java import java.util.ArrayList ; import java.util.List ; public class SmallestMultiple { // Function to generate all prime numbers up to n using // the Sieve of Eratosthenes public static List < Integer > sieveOfEratosthenes ( int n ) { boolean [] isPrime = new boolean [ n + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) { isPrime [ i ] = true ; } int p = 2 ; while ( p * p <= n ) { if ( isPrime [ p ] ) { for ( int i = p * p ; i <= n ; i += p ) { isPrime [ i ] = false ; } } p ++ ; } List < Integer > primeNumbers = new ArrayList <> (); for ( int i = 2 ; i <= n ; i ++ ) { if ( isPrime [ i ] ) { primeNumbers . add ( i ); } } return primeNumbers ; } // Function to find the smallest number divisible by all // numbers from 1 to n public static long smallestMultiple ( int n ) { List < Integer > primes = sieveOfEratosthenes ( n ); long lcm = 1 ; for ( int prime : primes ) { // Calculate the highest power of the prime that // is <= n int power = 1 ; while ( Math . pow ( prime power + 1 ) <= n ) { power ++ ; } lcm *= Math . pow ( prime power ); } return lcm ; } public static void main ( String [] args ) { int n = 20 ; System . out . println ( smallestMultiple ( n )); } }
Python import math def sieve_of_eratosthenes ( n ): '''Generate all prime numbers up to n.''' is_prime = [ True ] * ( n + 1 ) p = 2 while ( p * p <= n ): if ( is_prime [ p ] == True ): for i in range ( p * p n + 1 p ): is_prime [ i ] = False p += 1 prime_numbers = [ p for p in range ( 2 n + 1 ) if is_prime [ p ]] return prime_numbers def smallest_multiple ( n ): '''Find the smallest number divisible by all numbers from 1 to n.''' primes = sieve_of_eratosthenes ( n ) lcm = 1 for prime in primes : # Calculate the highest power of the prime that is <= n power = 1 while prime ** ( power + 1 ) <= n : power += 1 lcm *= prime ** power return lcm # Example usage: n = 20 print ( smallest_multiple ( n ))
JavaScript // Function to generate all prime numbers up to n using the // Sieve of Eratosthenes function sieveOfEratosthenes ( n ) { let isPrime = new Array ( n + 1 ). fill ( true ); let p = 2 ; while ( p * p <= n ) { if ( isPrime [ p ]) { for ( let i = p * p ; i <= n ; i += p ) { isPrime [ i ] = false ; } } p ++ ; } let primeNumbers = []; for ( let p = 2 ; p <= n ; p ++ ) { if ( isPrime [ p ]) { primeNumbers . push ( p ); } } return primeNumbers ; } // Function to find the smallest number divisible by all // numbers from 1 to n function smallestMultiple ( n ) { let primes = sieveOfEratosthenes ( n ); let lcm = 1 ; for ( let prime of primes ) { // Calculate the highest power of the prime that is // <= n let power = 1 ; while ( Math . pow ( prime power + 1 ) <= n ) { power ++ ; } lcm *= Math . pow ( prime power ); } return lcm ; } // Example usage: let n = 20 ; console . log ( smallestMultiple ( n ));
Saída
The smallest number divisible by all numbers from 1 to 20 is 232792560
Complexidade de tempo: O(nloglogn)
Espaço Auxiliar: Sobre)
