Given two positive integers N and K, the task is to find the value of N after incrementing the value of N in each operation by its smallest divisor exceeding N ( exceeding 1 ), exactly K times.
Examples:
Input: N = 5, K = 2
Output: 12
Explanation:
Smallest divisor of N (= 5) is 5. Therefore, N = 5 + 5 = 10.
Smallest divisor of N (= 10) is 2. Therefore, N = 5 + 2 = 12.
Therefore, the required output is 12.Input: N = 6, K = 4
Output: 14
Naive Approach: The simplest approach to solve this problem to iterate over the range [1, K] using variable i and in each operation, find the smallest divisors greater than 1 of N and increment the value of N by the smallest divisor greater than 1 of N. Finally, print the value of N.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the smallest// divisor of N greater than 1int smallestDivisorGr1(int N){ for (int i = 2; i <= sqrt(N); i++) { // If i is a divisor // of N if (N % i == 0) { return i; } } // If N is a prime number return N;}// Function to find the value of N by// performing the operations K timesint findValOfNWithOperat(int N, int K){ // Iterate over the range [1, K] for (int i = 1; i <= K; i++) { // Update N N += smallestDivisorGr1(N); } return N;}// Driver Codeint main(){ int N = 6, K = 4; cout << findValOfNWithOperat(N, K); return 0;} |
Java
// Java program to implement// the above approachclass GFG{// Function to find the smallest// divisor of N greater than 1static int smallestDivisorGr1(int N){ for (int i = 2; i <= Math.sqrt(N); i++) { // If i is a divisor // of N if (N % i == 0) { return i; } } // If N is a prime number return N;}// Function to find the value of N by// performing the operations K timesstatic int findValOfNWithOperat(int N, int K){ // Iterate over the range [1, K] for (int i = 1; i <= K; i++) { // Update N N += smallestDivisorGr1(N); } return N;}// Driver Codepublic static void main(String[] args){ int N = 6, K = 4; System.out.print(findValOfNWithOperat(N, K));}}// This code is contributed by shikhasingrajput |
Python3
# Python 3 program to implement# the above approachimport math# Function to find the smallest# divisor of N greater than 1def smallestDivisorGr1(N): for i in range(2, int(math.sqrt(N))+1): # If i is a divisor # of N if (N % i == 0): return i # If N is a prime number return N# Function to find the value of N by# performing the operations K timesdef findValOfNWithOperat(N, K): # Iterate over the range [1, K] for i in range(1, K + 1): # Update N N += smallestDivisorGr1(N) return N# Driver Codeif __name__ == "__main__": N = 6 K = 4 print(findValOfNWithOperat(N, K)) # This code is contributed by ukasp. |
C#
// C# program to implement// the above approachusing System;public class GFG{ // Function to find the smallest // divisor of N greater than 1 static int smallestDivisorGr1(int N) { for (int i = 2; i <= Math.Sqrt(N); i++) { // If i is a divisor // of N if (N % i == 0) { return i; } } // If N is a prime number return N; } // Function to find the value of N by // performing the operations K times static int findValOfNWithOperat(int N, int K) { // Iterate over the range [1, K] for (int i = 1; i <= K; i++) { // Update N N += smallestDivisorGr1(N); } return N; } // Driver Code public static void Main(String[] args) { int N = 6, K = 4; Console.Write(findValOfNWithOperat(N, K)); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program to implement// the above approach// Function to find the smallest// divisor of N greater than 1function smallestDivisorGr1(N){ for (let i = 2; i <= Math.sqrt(N); i++) { // If i is a divisor // of N if (N % i == 0) { return i; } } // If N is a prime number return N;}// Function to find the value of N by// performing the operations K timesfunction findValOfNWithOperat(N, K){ // Iterate over the range [1, K] for (let i = 1; i <= K; i++) { // Update N N += smallestDivisorGr1(N); } return N;}// Driver Codelet N = 6, K = 4;document.write(findValOfNWithOperat(N, K));// This code is contributed by Surbhi Tyagi.</script> |
Output:
14
Time Complexity: O(K * ?N)
Auxiliary Space: O(1)
Efficient Approach: Follow the steps below to solve the problem:
- If N is an even number then update the value of N to (N + K * 2).
- Otherwise, find the smallest positive divisor greater than 1 of N say, smDiv and update the value N to (N + smDiv + (K – 1) * 2)
- Finally, print the value of N.
Below is the implementation of the above approach:
C++14
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the smallest// divisor of N greater than 1int smallestDivisorGr1(int N){ for (int i = 2; i <= sqrt(N); i++) { // If i is a divisor // of N if (N % i == 0) { return i; } } // If N is a prime number return N;}// Function to find the value of N by// performing the operations K timesint findValOfNWithOperat(int N, int K){ // If N is an even number if (N % 2 == 0) { // Update N N += K * 2; } // If N is an odd number else { // Update N N += smallestDivisorGr1(N) + (K - 1) * 2; } return N;}// Driver Codeint main(){ int N = 6, K = 4; cout << findValOfNWithOperat(N, K); return 0;} |
Java
// Java program to implement// the above approachclass GFG{// Function to find the smallest// divisor of N greater than 1static int smallestDivisorGr1(int N){ for(int i = 2; i <= Math.sqrt(N); i++) { // If i is a divisor // of N if (N % i == 0) { return i; } } // If N is a prime number return N;} // Function to find the value of N by// performing the operations K timesstatic int findValOfNWithOperat(int N, int K){ // If N is an even number if (N % 2 == 0) { // Update N N += K * 2; } // If N is an odd number else { // Update N N += smallestDivisorGr1(N) + (K - 1) * 2; } return N;}// Driver Codepublic static void main(String[] args){ int N = 6, K = 4; System.out.print(findValOfNWithOperat(N, K));}}// This code is contributed by target_2 |
Python3
# Python program to implement# the above approach# Function to find the smallest# divisor of N greater than 1def smallestDivisorGr1(N): for i in range (sqrt(N)): i += 1 # If i is a divisor # of N if(N % i == 0): return i # If N is a prime number return N# Function to find the value of N by# performing the operations K timesdef findValOfNWithOperat(N, K): # If N is an even number if (N % 2 == 0): # Update N N += K * 2 # If N is an odd number else: # Update N N += smallestDivisorGr1(N) + (K - 1) * 2 return N# Driver CodeN = 6K = 4print(findValOfNWithOperat(N, K)) # This code is contributed by shivanisinghss2110 |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to find the smallest// divisor of N greater than 1static int smallestDivisorGr1(int N){ for(int i = 2; i <= Math.Sqrt(N); i++) { // If i is a divisor // of N if (N % i == 0) { return i; } } // If N is a prime number return N;} // Function to find the value of N by// performing the operations K timesstatic int findValOfNWithOperat(int N, int K){ // If N is an even number if (N % 2 == 0) { // Update N N += K * 2; } // If N is an odd number else { // Update N N += smallestDivisorGr1(N) + (K - 1) * 2; } return N;}// Driver codestatic public void Main(){ int N = 6, K = 4; Console.Write(findValOfNWithOperat(N, K));}}// This code is contributed by Khushboogoyal499 |
Javascript
<script>// Function to find the smallest// divisor of N greater than 1function smallestDivisorGr1( N){ for (var i = 2; i <= Math.sqrt(N); i++) { // If i is a divisor // of N if (N % i == 0) { return i; } } // If N is a prime number return N;}// Function to find the value of N by// performing the operations K timesfunction findValOfNWithOperat(N, K){ // If N is an even number if (N % 2 == 0) { // Update N N += K * 2; } // If N is an odd number else { // Update N N += smallestDivisorGr1(N) + (K - 1) * 2; } return N;}// Driver Codevar N = 6, K = 4; document.write(findValOfNWithOperat(N, K));</script> |
Output:
14
Time Complexity: O(?N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
