Dados dos números enteros N y K , la tarea es generar el resultado final de realizar K operaciones, lo que implica agregar el divisor más pequeño , que no sea 1, del valor actual de N en cada paso.
Ejemplo:
Entrada: N = 9, K = 4
Salida: 18
Explicación:
Los divisores de 9 son {1, 3, 9}
1ra Operación: N = 9 + 3 = 12
2da Operación: N = 12 + 2 = 14
3ra Operación: N = 14 + 2 = 16
4ª Operación: N = 16 + 2 = 18
Entrada: N = 16, K = 3
Salida: 22
Enfoque ingenuo: el enfoque de fuerza bruta para este problema es realizar la operación K veces y luego imprimir el número final.
Enfoque eficiente: el truco aquí es que si el N dado es par , el divisor más pequeño siempre será 2 para todas las operaciones K. Por lo tanto, el número K -ésimo requerido será simplemente
número requerido = N + K * 2
Además , si N es impar , el divisor más pequeño será impar. Por lo tanto, sumarlos dará como resultado un valor par (impar + impar = par). Por lo tanto, ahora el truco anterior se puede aplicar para operaciones (K-1), es decir,
número requerido = N + divisor más pequeño de N + (K – 1) * 2
A continuación se muestra la implementación del enfoque anterior:
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>
18
Complejidad del tiempo: O(√N )