Mazākais skaitlis, kas dalās ar pirmajiem n skaitļiem
Izmēģiniet to GfG Practice 
Izvade
Dots skaitlis n atrodiet mazāko skaitli, kas vienmērīgi dalās ar katru skaitli no 1 līdz n.
Piemēri:
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
Ja uzmanīgi novērojat gadiem jābūt LCM no skaitļiem no 1 līdz n .
Lai atrastu skaitļu LCM no 1 līdz n -
- Inicializēt ans = 1.
- Atkārtojiet visus skaitļus no i = 1 līdz i = n.
I'tajā iterācijā ans = LCM(1 2 …….. i) . To var izdarīt viegli kā LCM(1 2…. i) = LCM(ans i) .
Tādējādi i' iterācijā mums vienkārši jādara -
ans = LCM(ans i) = ans * i / gcd(ans i) [Using the below property a*b = gcd(ab) * lcm(ab)]C++
Piezīme: C++ kodā atbilde ātri pārsniedz veselo skaitļu robežu pat garo garo ierobežojumu.
Zemāk ir loģikas īstenošana.
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 ));
Izvade232792560Laika sarežģītība: O(n log2n) jo _gcd(ab) sarežģītība c++ ir log2n un tas tiek izpildīts n reizes ciklā.
Palīgtelpa: O(1)
Iepriekš minētais risinājums lieliski darbojas vienai ievadei. Bet, ja mums ir vairākas ievades, ir ieteicams izmantot Eratosthenes sietu, lai saglabātu visus galvenos faktorus. Lūdzu, skatiet zemāk esošo rakstu par pieeju, kas balstīta uz sietu.Pieeja : [Izmantojot Eratostena siets ]
Lai efektīvāk atrisinātu problēmu atrast mazāko skaitli, kas dalās ar pirmajiem “n” skaitļiem, mēs varam izmantot Eratostena sietu, lai iepriekš aprēķinātu pirmskaitļus līdz “n”. Tad mēs varam izmantot šos pirmskaitļus, lai efektīvāk aprēķinātu mazāko kopējo daudzkārtni (LCM), ņemot vērā katra pirmskaitļa augstākās pakāpes, kas ir mazākas vai vienādas ar “n”.
Soli pa solim pieeja:
- Ģenerēt pirmskaitļus līdz n: Izmantojiet Eratosthenes sietu, lai atrastu visus pirmskaitļus līdz “n”.
- Aprēķiniet LCM, izmantojot šos Primes: Katram pirmskaitļam nosaka šī pirmskaitļa augstāko jaudu, kas ir mazāka vai vienāda ar “n”. Reiziniet šīs augstākās spējas kopā, lai iegūtu LCM
Zemāk ir aprakstīta iepriekš minētās pieejas īstenošana:
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 ));
Izvade
The smallest number divisible by all numbers from 1 to 20 is 232792560
Laika sarežģītība: O(nloglogn)
Palīgtelpa: O(n)
