# Number formed after K times repeated addition of smallest divisor of N

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 = 4Output:18Explanation:

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 = 18Input:N = 16, K = 3Output:22

**Naive Approach:** The brute force approach for this problem is to perform the operation K times and then print th 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 K

^{th}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 code` `int` `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 N` `import` `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 code` `public` `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 N` `import` `math` `def` `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 code` `if` `__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 N` `using` `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 code` `public` `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 N` `function` `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 code` `let N = 9;` `let K = 4;` ` ` `FindValue( N, K );` `// This code is contributed by Surbhi Tyagi.` `</script>` |

**Output:**

18

**Time complexity: **O(√N )

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**