Modifique N sumando su divisor positivo más pequeño exactamente K veces

Posted on by Rudeus Greyrat

Dados dos enteros positivos N y K , la tarea es encontrar el valor de N después de incrementar el valor de N en cada operación por su divisor más pequeño que exceda N ( excediendo 1 ), exactamente K veces.

Ejemplos:

Entrada: N = 5, K = 2 
Salida: 12 
Explicación: 
El divisor más pequeño de N (= 5) es 5. Por lo tanto, N = 5 + 5 = 10. El 
divisor más pequeño de N (= 10) es 2. Por lo tanto, N = 5 + 2 = 12. 
Por lo tanto, la salida requerida es 12.

Entrada: N = 6, K = 4 
Salida: 14

Enfoque ingenuo: el enfoque más simple para resolver este problema es iterar sobre el rango [1, K] usando la variable i y en cada operación, encontrar los divisores más pequeños mayores que 1 de N e incrementar el valor de N por el divisor más pequeño mayor que 1 de n _ Finalmente, imprima el valor de N .

A continuación se muestra la implementación del enfoque anterior:

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 1
int 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 times
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
int main()
{
    int N = 6, K = 4;
 
    cout << findValOfNWithOperat(N, K);
    return 0;
}

Java

// Java program to implement
// the above approach
 
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;
 
    System.out.print(findValOfNWithOperat(N, K));
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python 3 program to implement
# the above approach
import math
 
# Function to find the smallest
# divisor of N greater than 1
def 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 times
def findValOfNWithOperat(N, K):
 
    # Iterate over the range [1, K]
    for i in range(1, K + 1):
 
        # Update N
        N += smallestDivisorGr1(N)
 
    return N
 
# Driver Code
if __name__ == "__main__":
 
    N = 6
    K = 4
 
    print(findValOfNWithOperat(N, K))
 
    # This code is contributed by ukasp.

C#

// C# program to implement
// the above approach
using 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 1
function 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 times
function findValOfNWithOperat(N, K)
{
 
    // Iterate over the range [1, K]
    for (let i = 1; i <= K; i++)
    {
 
        // Update N
        N += smallestDivisorGr1(N);
    }
    return N;
}
 
// Driver Code
let N = 6, K = 4;
document.write(findValOfNWithOperat(N, K));
 
// This code is contributed by Surbhi Tyagi.
</script>
Producción: 

14

 

Complejidad de Tiempo: O(K * √N)  
Espacio Auxiliar: O(1)

Enfoque eficiente: siga los pasos a continuación para resolver el problema:

  • Si N es un número par , actualice el valor de N a (N + K * 2) .
  • De lo contrario, encuentre el divisor positivo más pequeño mayor que 1 de N , por ejemplo, smDiv y actualice el valor N a (N + smDiv + (K – 1) * 2)
  • Finalmente, imprima el valor de N .

A continuación se muestra la implementación del enfoque anterior:

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 1
int 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 times
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 Code
int main()
{
    int N = 6, K = 4;
 
    cout << findValOfNWithOperat(N, K);
    return 0;
}

Java

// Java program to implement
// the above approach
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)
{
     
    // 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 Code
public 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 1
def 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 times
def 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 Code
N = 6
K = 4
print(findValOfNWithOperat(N, K))
    
# This code is contributed by shivanisinghss2110

C#

// C# program to implement
// the above approach
using System;
 
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)
{
     
    // 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 code
static 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 1
function 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 times
function 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 Code
var N = 6, K = 4;
 
    document.write(findValOfNWithOperat(N, K));
 
 
 
</script>
Producción: 

14

 

Complejidad de Tiempo: O(√N)  
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por krish_45 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 *