Given two integers N and K, the task is to generate the final outcome of performing K operations which involves adding the smallest divisor, other than 1, of the current value of N to it at every step.
Example:
Input: N = 9, K = 4
Output: 18
Explanation:
Divisors of 9 are {1, 3, 9}
1st Operation: N = 9 + 3 = 12
2nd Operation: N = 12 + 2 = 14
3rd Operation: N = 14 + 2 = 16
4th Operation: N = 16 + 2 = 18
Input: N = 16, K = 3
Output: 22
Naive Approach: The brute force approach for this problem is to perform the operation K times and then print the final number.
Efficient Approach: The trick here is that if the given N is even, smallest divisor will be always 2 for all the K operations. Hence, the required Kth number will be simply
required number = N + K * 2
Also if N is odd, the smallest divisor will be odd. Hence adding them will result in an even value (odd + odd = even). Therefore now the above trick can be applied for (K-1) operations, i.e.,
required number = N + smallest divisor of N + (K – 1) * 2
Below is the implementation of the above approach:
C++
// C++ program to find the Kth number // formed after repeated addition of// smallest divisor of N#include<bits/stdc++.h>#include <cmath> using namespace std;void FindValue(int N, int K){ // If N is even if( N % 2 == 0 ) { N = N + 2 * K; } // If N is odd else { int i; for(i = 2; i < sqrt(N) + 1; i++) { if(N % i == 0) break; } // Add smallest divisor to N N = N + i; // Updated N is even N = N + 2 * ( K - 1 ); } cout << N << endl;} // Driver codeint main(){ int N = 9; int K = 4; FindValue( N, K );} // This code is contributed by Surendra_Gangwar |
Java
// Java program to find the Kth number // formed after repeated addition of// smallest divisor of Nimport java.util.*;class GFG{static void FindValue(int N, int K){ // If N is even if( N % 2 == 0 ) { N = N + 2 * K; } // If N is odd else { int i; for(i = 2; i < Math.sqrt(N) + 1; i++) { if(N % i == 0) break; } // Add smallest divisor to N N = N + i; // Updated N is even N = N + 2 * ( K - 1 ); } System.out.print(N);} // Driver codepublic static void main(String args[]){ int N = 9; int K = 4; FindValue( N, K );}}// This code is contributed by Nidhi_biet |
Python3
# Python3 program to find the # Kth number formed after # repeated addition of # smallest divisor of Nimport mathdef FindValue(N, K): # If N is even if( N % 2 == 0 ): N = N + 2 * K # If N is odd else: # Find the smallest divisor for i in range( 2, (int)(math.sqrt(N))+1 ): if( N % i == 0): break # Add smallest divisor to N N = N + i # Updated N is even N = N + 2 * ( K - 1 ) print(N)# Driver codeif __name__ == "__main__": N = 9 K = 4 FindValue( N, K ) |
C#
// C# program to find the Kth number // formed after repeated addition of// smallest divisor of Nusing System;class GFG{static void FindValue(int N, int K){ // If N is even if( N % 2 == 0 ) { N = N + 2 * K; } // If N is odd else { int i; for(i = 2; i < Math.Sqrt(N) + 1; i++) { if(N % i == 0) break; } // Add smallest divisor to N N = N + i; // Updated N is even N = N + 2 * ( K - 1 ); } Console.WriteLine(N);} // Driver codepublic static void Main(){ int N = 9; int K = 4; FindValue( N, K );}}// This code is contributed by Code_Mech |
Javascript
<script>// JavaScript program to find the Kth number// formed after repeated addition of// smallest divisor of Nfunction FindValue(N, K){ // If N is even if( N % 2 == 0 ) { N = N + 2 * K; } // If N is odd else { let i; for(i = 2; i < Math.sqrt(N) + 1; i++) { if(N % i == 0) break; } // Add smallest divisor to N N = N + i; // Updated N is even N = N + 2 * ( K - 1 ); } document.write(N + "<br>");} // Driver codelet N = 9;let K = 4; FindValue( N, K );// This code is contributed by Surbhi Tyagi.</script> |
18
Time complexity: O(?N )
Space Complexity: O(1)
