İlk n sayıya bölünebilen en küçük sayı
GfG Practice'de deneyin 
Çıkış
Bir sayı verildi N 1'den n'ye kadar olan sayılara bölünebilen en küçük sayıyı bulun.
Örnekler:
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
Dikkatlice gözlemlerseniz yıllar olmalı 1'den n'ye kadar sayıların LCM'si .
1'den n'e kadar sayıların LCM'sini bulmak için -
- Ans = 1'i başlat.
- i = 1'den i = n'ye kadar tüm sayıları yineleyin.
i'inci yinelemede ans = LCM(1 2 …….. i) . Bu kolayca yapılabilir LCM(1 2 ….i) = LCM(ve i) .
Yani i’’ yinelemede yapmamız gereken tek şey -
ans = LCM(ans i) = ans * i / gcd(ans i) [Using the below property a*b = gcd(ab) * lcm(ab)]C++
Not : C++ kodunda yanıt, uzun uzun sınırı bile hızla tamsayı sınırını aşar.
Aşağıda mantığın uygulanması verilmiştir.
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 ));
Çıkış232792560Zaman Karmaşıklığı: O(n log2n) c++'da _gcd(ab)'nin karmaşıklığı log2n olduğundan ve bu bir döngüde n kez çalıştığından.
Yardımcı Alan: O(1)
Yukarıdaki çözüm tek bir giriş için gayet iyi çalışıyor. Ancak birden fazla girdimiz varsa, tüm asal çarpanları depolamak için Eratosthenes Eleği'ni kullanmak iyi bir fikirdir. Elek tabanlı yaklaşım için lütfen aşağıdaki makaleye bakın.Yaklaşım: [Kullanarak Eratostenes Eleği ]
İlk 'n' sayılarına bölünebilen en küçük sayıyı bulma problemini daha verimli bir şekilde çözmek için, 'n'ye kadar asal sayıları önceden hesaplamak için Eratosthenes Eleği'ni kullanabiliriz. Daha sonra bu asal sayıları, 'n'den küçük veya ona eşit olan her asal sayının en yüksek kuvvetlerini dikkate alarak en küçük ortak katı (LCM) daha verimli bir şekilde hesaplamak için kullanabiliriz.
Adım Adım Yaklaşım:
- N'ye kadar Asal Sayılar oluşturun: 'n'ye kadar olan tüm asal sayıları bulmak için Eratosthenes Eleği'ni kullanın.
- Bu Asal Sayıları kullanarak LCM'yi hesaplayın: Her asal sayı için, o asalın 'n'den küçük veya ona eşit olan en yüksek kuvvetini belirleyin. LCM'yi elde etmek için bu en yüksek güçleri çarpın
Yukarıdaki yaklaşımın uygulanması aşağıdadır:
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 ));
Çıkış
The smallest number divisible by all numbers from 1 to 20 is 232792560
Zaman Karmaşıklığı: O(nloglogn)
Yardımcı Alan: Açık)
