1이 되는 숫자 n이 주어지면<= N <= 10^6 the Task is to Find the LCM of First n Natural Numbers.
예:
Input : n = 5 Output : 60 Input : n = 6 Output : 60 Input : n = 7 Output : 420
솔루션으로 넘어가기 전에 여기를 클릭하여 연습해 보시기를 적극 권장합니다.
아래 기사에서 간단한 해결책을 논의했습니다.
처음 n개 숫자로 나눌 수 있는 가장 작은 숫자
위의 솔루션은 단일 입력에 적합합니다. 하지만 입력이 여러 개라면 다음을 사용하는 것이 좋습니다. 에라토스테네스의 체 모든 소인수를 저장합니다. LCM(a b) = X이면 알 수 있듯이 a 또는 b의 소인수는 'X'의 소인수도 됩니다.
- 1로 lcm 변수를 초기화합니다.
- 길이가 10^6인 에라토스테네스 체(부울 벡터 isPrime)를 생성합니다(이상적으로는 계승의 자릿수와 같아야 함).
- 이제 bool 벡터 isPrime의 각 숫자에 대해 숫자가 소수인 경우(isPrime[i]가 true임) 주어진 숫자보다 작고 소수의 거듭제곱과 같은 최대 숫자를 찾습니다.
- 그런 다음 이 숫자에 lcm 변수를 곱합니다.
- 소수가 주어진 숫자보다 작아질 때까지 3단계와 4단계를 반복합니다.
삽화:
For example if n = 10 8 will be the first number which is equal to 2^3 then 9 which is equal to 3^2 then 5 which is equal to 5^1 then 7 which is equal to 7^1 Finally we multiply those numbers 8*9*5*7 = 2520
아래는 위의 아이디어를 구현한 것입니다.
C++// C++ program to find LCM of First N Natural Numbers. #include
// Java program to find LCM of First N Natural Numbers. import java.util.*; class GFG { static int MAX = 100000; // array to store all prime less than and equal to 10^6 static ArrayList<Integer> primes = new ArrayList<Integer>(); // utility function for sieve of sieve of Eratosthenes static void sieve() { boolean[] isComposite = new boolean[MAX + 1]; for (int i = 2; i * i <= MAX; i++) { if (isComposite[i] == false) for (int j = 2; j * i <= MAX; j++) isComposite[i * j] = true; } // Store all prime numbers in vector primes[] for (int i = 2; i <= MAX; i++) if (isComposite[i] == false) primes.add(i); } // Function to find LCM of first n Natural Numbers static long LCM(int n) { long lcm = 1; for (int i = 0; i < primes.size() && primes.get(i) <= n; i++) { // Find the highest power of prime primes[i] // that is less than or equal to n int pp = primes.get(i); while (pp * primes.get(i) <= n) pp = pp * primes.get(i); // multiply lcm with highest power of prime[i] lcm *= pp; lcm %= 1000000007; } return lcm; } // Driver code public static void main(String[] args) { sieve(); int N = 7; // Function call System.out.println(LCM(N)); } } // This code is contributed by mits
# Python3 program to find LCM of # First N Natural Numbers. MAX = 100000 # array to store all prime less # than and equal to 10^6 primes = [] # utility function for # sieve of Eratosthenes def sieve(): isComposite = [False]*(MAX+1) i = 2 while (i * i <= MAX): if (isComposite[i] == False): j = 2 while (j * i <= MAX): isComposite[i * j] = True j += 1 i += 1 # Store all prime numbers in # vector primes[] for i in range(2 MAX+1): if (isComposite[i] == False): primes.append(i) # Function to find LCM of # first n Natural Numbers def LCM(n): lcm = 1 i = 0 while (i < len(primes) and primes[i] <= n): # Find the highest power of prime # primes[i] that is less than or # equal to n pp = primes[i] while (pp * primes[i] <= n): pp = pp * primes[i] # multiply lcm with highest # power of prime[i] lcm *= pp lcm %= 1000000007 i += 1 return lcm # Driver code sieve() N = 7 # Function call print(LCM(N)) # This code is contributed by mits
// C# program to find LCM of First N // Natural Numbers. using System.Collections; using System; class GFG { static int MAX = 100000; // array to store all prime less than // and equal to 10^6 static ArrayList primes = new ArrayList(); // utility function for sieve of // sieve of Eratosthenes static void sieve() { bool[] isComposite = new bool[MAX + 1]; for (int i = 2; i * i <= MAX; i++) { if (isComposite[i] == false) for (int j = 2; j * i <= MAX; j++) isComposite[i * j] = true; } // Store all prime numbers in vector primes[] for (int i = 2; i <= MAX; i++) if (isComposite[i] == false) primes.Add(i); } // Function to find LCM of first // n Natural Numbers static long LCM(int n) { long lcm = 1; for (int i = 0; i < primes.Count && (int)primes[i] <= n; i++) { // Find the highest power of prime primes[i] // that is less than or equal to n int pp = (int)primes[i]; while (pp * (int)primes[i] <= n) pp = pp * (int)primes[i]; // multiply lcm with highest power of prime[i] lcm *= pp; lcm %= 1000000007; } return lcm; } // Driver code public static void Main() { sieve(); int N = 7; // Function call Console.WriteLine(LCM(N)); } } // This code is contributed by mits
<script> // Javascript program to find LCM of First N // Natural Numbers. let MAX = 100000; // array to store all prime less than // and equal to 10^6 let primes = []; // utility function for sieve of // sieve of Eratosthenes function sieve() { let isComposite = new Array(MAX + 1); isComposite.fill(false); for (let i = 2; i * i <= MAX; i++) { if (isComposite[i] == false) for (let j = 2; j * i <= MAX; j++) isComposite[i * j] = true; } // Store all prime numbers in vector primes[] for (let i = 2; i <= MAX; i++) if (isComposite[i] == false) primes.push(i); } // Function to find LCM of first // n Natural Numbers function LCM(n) { let lcm = 1; for (let i = 0; i < primes.length && primes[i] <= n; i++) { // Find the highest power of prime primes[i] // that is less than or equal to n let pp = primes[i]; while (pp * primes[i] <= n) pp = pp * primes[i]; // multiply lcm with highest power of prime[i] lcm *= pp; lcm %= 1000000007; } return lcm; } sieve(); let N = 7; // Function call document.write(LCM(N)); // This code is contributed by decode2207. </script>
// PHP program to find LCM of // First N Natural Numbers. $MAX = 100000; // array to store all prime less // than and equal to 10^6 $primes = array(); // utility function for // sieve of Eratosthenes function sieve() { global $MAX $primes; $isComposite = array_fill(0 $MAX false); for ($i = 2; $i * $i <= $MAX; $i++) { if ($isComposite[$i] == false) for ($j = 2; $j * $i <= $MAX; $j++) $isComposite[$i * $j] = true; } // Store all prime numbers in // vector primes[] for ($i = 2; $i <= $MAX; $i++) if ($isComposite[$i] == false) array_push($primes $i); } // Function to find LCM of // first n Natural Numbers function LCM($n) { global $MAX $primes; $lcm = 1; for ($i = 0; $i < count($primes) && $primes[$i] <= $n; $i++) { // Find the highest power of prime // primes[i] that is less than or // equal to n $pp = $primes[$i]; while ($pp * $primes[$i] <= $n) $pp = $pp * $primes[$i]; // multiply lcm with highest // power of prime[i] $lcm *= $pp; $lcm %= 1000000007; } return $lcm; } // Driver code sieve(); $N = 7; // Function call echo LCM($N); // This code is contributed by mits ?> 산출
420
시간 복잡도 : 에2)
보조 공간: 에)
또 다른 접근법:
아이디어는 숫자가 3보다 작으면 숫자를 반환한다는 것입니다. 숫자가 2보다 크면 nn-1의 LCM을 찾습니다.
- x=LCM(nn-1)이라고 가정해 보겠습니다.
- 다시 x=LCM(xn-2)
- 다시 x=LCM(xn-3) ...
- .
- .
- 다시 x=LCM(x1) ...
이제 결과는 x입니다.
LCM(ab)을 찾기 위해 (ab)의 HCF를 반환하는 hcf(ab) 함수를 사용합니다.
우리는 그것을 알고 있습니다 LCM(ab)= (a*b)/HCF(ab)
삽화:
For example if n = 7 function call lcm(76) now lets say a=7 b=6 Now b!= 1 Hence a=lcm(76) = 42 and b=6-1=5 function call lcm(425) a=lcm(425) = 210 and b=5-1=4 function call lcm(2104) a=lcm(2104) = 420 and b=4-1=3 function call lcm(4203) a=lcm(4203) = 420 and b=3-1=2 function call lcm(4202) a=lcm(4202) = 420 and b=2-1=1 Now b=1 Hence return a=420
아래는 위의 접근 방식을 구현한 것입니다.
C++// C++ program to find LCM of First N Natural Numbers. #include
// Java program to find LCM of First N Natural Numbers public class Main { // to calculate hcf static int hcf(int a int b) { if (b == 0) return a; return hcf(b a % b); } static int findlcm(int aint b) { if (b == 1) // lcm(ab)=(a*b)/hcf(ab) return a; // assign a=lcm of nn-1 a = (a * b) / hcf(a b); // b=b-1 b -= 1; return findlcm(a b); } // Driver code. public static void main(String[] args) { int n = 7; if (n < 3) System.out.print(n); // base case else // Function call // pass nn-1 in function to find LCM of first n natural // number System.out.print(findlcm(n n - 1)); } } // This code is contributed by divyeshrabadiya07.
# Python3 program to find LCM # of First N Natural Numbers. # To calculate hcf def hcf(a b): if (b == 0): return a return hcf(b a % b) def findlcm(a b): if (b == 1): # lcm(ab)=(a*b)//hcf(ab) return a # Assign a=lcm of nn-1 a = (a * b) // hcf(a b) # b=b-1 b -= 1 return findlcm(a b) # Driver code n = 7 if (n < 3): print(n) else: # Function call # pass nn-1 in function # to find LCM of first n # natural number print(findlcm(n n - 1)) # This code is contributed by Shubham_Singh
// C# program to find LCM of First N Natural Numbers. using System; class GFG { // to calculate hcf static int hcf(int a int b) { if (b == 0) return a; return hcf(b a % b); } static int findlcm(int aint b) { if (b == 1) // lcm(ab)=(a*b)/hcf(ab) return a; // assign a=lcm of nn-1 a = (a * b) / hcf(a b); // b=b-1 b -= 1; return findlcm(a b); } // Driver code static void Main() { int n = 7; if (n < 3) Console.Write(n); // base case else // Function call // pass nn-1 in function to find LCM of first n natural // number Console.Write(findlcm(n n - 1)); } } // This code is contributed by divyesh072019.
<script> // Javascript program to find LCM of First N Natural Numbers. // to calculate hcf function hcf(a b) { if (b == 0) return a; return hcf(b a % b); } function findlcm(ab) { if (b == 1) // lcm(ab)=(a*b)/hcf(ab) return a; // assign a=lcm of nn-1 a = (a * b) / hcf(a b); // b=b-1 b -= 1; return findlcm(a b); } let n = 7; if (n < 3) document.write(n); // base case else // Function call // pass nn-1 in function to find LCM of first n natural // number document.write(findlcm(n n - 1)); </script>
산출
420
시간 복잡도 : O(n 로그 n)
보조 공간: 오(1)