Número formado después de K multiplicado por la suma repetida del divisor más pequeño de N

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>
Producción: 

18

 

Complejidad del tiempo: O(√N )
 

Publicación traducida automáticamente

Artículo escrito por Versus y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *