A legkisebb szám, amely osztható az első n számmal
Próbáld ki a GfG Practice-n 
Kimenet
Adott egy szám n keresse meg a legkisebb számmal egyenlően osztható számot 1-től n-ig.
Példák:
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
Ha figyelmesen megfigyeli a évre kell lennie a Az 1-től n-ig terjedő számok LCM-je .
Az 1-től n-ig terjedő számok LCM-jének megtalálása -
- Inicializálás ans = 1.
- Ismételje meg az összes számot i = 1-től i = n-ig.
Az i-edik iterációnál ans = LCM(1 2 …….. i) . Ez könnyen megtehető, mint LCM(1 2 …. i) = LCM(ans i) .
Így az i-ik iterációnál csak azt kell tennünk,
ans = LCM(ans i) = ans * i / gcd(ans i) [Using the below property a*b = gcd(ab) * lcm(ab)]C++
Megjegyzés: A C++ kódban a válasz gyorsan túllépi az egész szám határt, még a hosszú hosszú határt is.
Alább látható a logika megvalósítása.
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 ));
Kimenet232792560Időbonyolultság: O(n log2n) mivel a _gcd(ab) összetettsége c++-ban log2n és ez n-szer fut le egy ciklusban.
Segédtér: O(1)
A fenti megoldás egyetlen bemenetre is jól működik. De ha több bemenetünk van, akkor jó ötlet az Eratosthenes szitát használni az összes elsődleges tényező tárolására. Kérjük, olvassa el az alábbi cikket a szita alapú megközelítésről.Megközelítés: [Használ Eratoszthenész szita ]
Az első 'n' számmal osztható legkisebb szám megtalálásának problémájának hatékonyabb megoldása érdekében az Eratoszthenész szitáját használhatjuk az 'n'-ig terjedő prímszámok előszámítására. Ezután ezeket a prímszámokat a legkisebb közös többszörös (LCM) hatékonyabb kiszámítására használhatjuk, ha figyelembe vesszük az egyes prímek azon legnagyobb hatványait, amelyek kisebbek vagy egyenlőek 'n'-nél.
Lépésről lépésre történő megközelítés:
- Prímszámok generálása n-ig: Használja Eratosthenes szitáját, hogy megtalálja az összes prímszámot 'n'-ig.
- Számítsa ki az LCM-et a következő primek használatával: Minden prímhez határozza meg annak a prímnek a legmagasabb hatványát, amely kisebb vagy egyenlő, mint 'n'. Szorozzuk meg ezeket a legmagasabb teljesítményeket, hogy megkapjuk az LCM-et
Az alábbiakban bemutatjuk a fenti megközelítés megvalósítását:
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 ));
Kimenet
The smallest number divisible by all numbers from 1 to 20 is 232792560
Időbeli összetettség: O(nloglogn)
Kiegészítő tér: On)
