k-Número aproximado o k-Número irregular

Un número k-áspero o k-irregular es un número cuyo factor primo más pequeño es mayor o igual que el número ‘k’. Dados los números ‘n’ y ‘k’ como entrada, debemos encontrar si ‘n; es un k-número aproximado o no.
Ejemplos:
 

Entrada: n = 10, k = 2 
Salida: 10 es un número aproximado de 2 
Explicación: Los factores primos de 10 son 2 y 5 Por lo tanto, su factor primo más pequeño es 2, que es mayor o igual que k, es decir, 2 
Entrada: n = 55, k = 7 
Resultado: 55 no es un número aproximado de 7 
Explicación: los factores primos de 55 son 5 y 11 Por lo tanto, su factor primo más pequeño es 5, que no es mayor ni igual que k, es decir, 7

Se puede inferir de lo anterior que cada entero positivo, excepto 1, es un número aproximado de 2 ya que su factor primo más pequeño es 2 (para enteros positivos pares) o mayor que 2 (para enteros positivos impares).
 

Enfoque simple

1. Primero encuentra todos los números primos hasta el número ‘n’.
2. A continuación, encuentre el factor primo más pequeño del número ‘n’ a partir de su descomposición en factores primos.
3. Comprueba si el factor primo más pequeño es mayor o igual que ‘k’ o no.

// CPP to check if n is a k-rough number
// or not
#include <bits/stdc++.h>
using namespace std;
 
// Finds primes by Sieve of Eratosthenes
// method
vector<int> getPrimes(int n)
{
    int i, j;
    bool isPrime[n + 1];
    memset(isPrime, true, sizeof(isPrime));
    for (i = 2; i * i <= n; i++)
    {
 
        // If isPrime[i] is not changed,
        // then it is prime
        if (isPrime[i] == true)
        {
            // Update all multiples of p
            for (j = i * 2; j <= n; j += i)
                isPrime[j] = false;
        }
    }
 
    // Forming array of the prime numbers found
    vector<int> primes;
    for (i = 2; i <= n; i++)
        if (isPrime[i])
            primes.push_back(i);
    return primes;
}
 
// Checking whether a number is k-rough or not
bool isRough(int n, int k)
{
    vector<int> primes = getPrimes(n);
 
    // Finding minimum prime factor of n
    int min_pf = n;
    for (int i = 0; i < primes.size(); i++)
        if (n % primes[i] == 0)
            min_pf = primes[i];
 
    // Return true if minimum prime factor
    // is greater than or equal to k. Else
    // return false.
    return (min_pf >= k);
}
 
// Driver Method
int main()
{
    int n = 75, k = 3;
    if (isRough(n, k))
        cout << n << " is a "
            << k << "-rough number\n";
    else
        cout << n << " is not a "
            << k << "-rough number\n";
    return 0;
}

// Java to check if n is
// a k-rough number or not
import java.io.*;
import java.util.*;
 
class GFG
{
     
    // Finds primes by Sieve
    // of Eratosthenes method
    static ArrayList<Integer> getPrimes(int n)
    {
        int i, j;
        int []isPrime = new int[n + 1];
         
        for(i = 0; i < n + 1; i++)
            isPrime[i] = 1;
         
        for (i = 2; i * i <= n; i++)
        {    
            // If isPrime[i] is not
            // changed, then it is prime
            if (isPrime[i] == 1)
            {
                // Update all
                // multiples of p
                for (j = i * 2; j <= n; j += i)
                    isPrime[j] = 0;
            }
        }
     
        // Forming array of the
        // prime numbers found
        ArrayList<Integer> primes = new ArrayList<Integer>();
        for (i = 2; i <= n; i++)
            if (isPrime[i] == 1)
                primes.add(i);
        return primes;
    }
     
    // Checking whether a
    // number is k-rough or not
    static boolean isRough(int n, int k)
    {
        ArrayList<Integer> primes = getPrimes(n);
         
        // Finding minimum
        // prime factor of n
        int min_pf = n;
        for (int i = 0; i < primes.size(); i++)
            if (n % primes.get(i) == 0)
                min_pf = primes.get(i);
     
        // Return true if minimum
        // prime factor is greater
        // than or equal to k. Else
        // return false.
        return (min_pf >= k);
    }
     
    // Driver Code
    public static void main(String args[])
    {
        int n = 75, k = 3;
        if (isRough(n, k))
            System.out.print(n + " is a " + k +
                            "-rough number\n");
        else
            System.out.print(+ n + " is not a " +
                          k + "-rough number\n");
    }
}
// This code is contributed by
// Manish Shaw.(manishshaw1)

# Python3 to check if n is a k-rough
# number or not
 
# Finds primes by Sieve of Eratosthenes method
def getPrimes(n):
 
    isPrime = [True] * (n + 1);
    i = 2;
    while (i * i <= n):
 
        # If isPrime[i] is not changed,
        # then it is prime
        if (isPrime[i] == True):
             
            # Update all multiples of p
            j = i * 2;
            while (j <= n):
                isPrime[j] = False;
                j += i;
        i += 1;
 
    # Forming array of the
    # prime numbers found
    primes = [];
    for i in range(2, n + 1):
        if (isPrime[i]):
            primes.append(i);
    return primes;
 
# Checking whether a
# number is k-rough or not
def isRough(n, k):
 
    primes = getPrimes(n);
 
    # Finding minimum
    # prime factor of n
    min_pf = n;
    for i in range(len(primes)):
        if (n % primes[i] == 0):
            min_pf = primes[i];
 
    # Return true if minimum
    # prime factor is greater
    # than or equal to k. Else
    # return false.
    return (min_pf >= k);
 
# Driver Code
n = 75;
k = 3;
if (isRough(n, k)):
    print(n, "is a", k,"-rough number");
else:
    print(n, "is not a", k, "-rough number");
         
# This code is contributed by mits

// C# to check if n is a k-rough number
// or not
using System;
using System.Collections.Generic;
using System.Linq;
 
class GFG {
     
    // Finds primes by Sieve of Eratosthenes
    // method
    static List<int> getPrimes(int n)
    {
        int i, j;
        int []isPrime = new int[n + 1];
         
        for(i = 0; i < n + 1; i++)
            isPrime[i] = 1;
        // Array.Clear(isPrime, 1, isPrime.Length);
         
        for (i = 2; i * i <= n; i++)
        {
     
            // If isPrime[i] is not changed,
            // then it is prime
            if (isPrime[i] == 1)
            {
                // Update all multiples of p
                for (j = i * 2; j <= n; j += i)
                    isPrime[j] = 0;
            }
        }
     
        // Forming array of the prime numbers
        // found
        List<int> primes = new List<int>();
        for (i = 2; i <= n; i++)
            if (isPrime[i] == 1)
                primes.Add(i);
        return primes;
    }
     
    // Checking whether a number is k-rough
    // or not
    static bool isRough(int n, int k)
    {
        List<int> primes = getPrimes(n);
         
        // Finding minimum prime factor of n
        int min_pf = n;
        for (int i = 0; i < primes.Count; i++)
            if (n % primes[i] == 0)
                min_pf = primes[i];
     
        // Return true if minimum prime factor
        // is greater than or equal to k. Else
        // return false.
        return (min_pf >= k);
    }
     
    // Driver Method
    static void Main()
    {
        int n = 75, k = 3;
        if (isRough(n, k))
            Console.Write(n + " is a " + k +
                         "-rough number\n");
        else
            Console.Write(+ n + " is not a "
                   + k + "-rough number\n");
    }
}
 
// This code is contributed by manishshaw.

<?php
// PHP to check if n is
// a k-rough number or not
 
// Finds primes by Sieve
// of Eratosthenes method
function getPrimes($n)
{
    $isPrime = array_fill(0, ($n + 1), true);
    for ($i = 2;
         $i * $i <= $n; $i++)
    {
 
        // If isPrime[i] is
        // not changed,
        // then it is prime
        if ($isPrime[$i] == true)
        {
            // Update all
            // multiples of p
            for ($j = $i * 2;
                 $j <= $n; $j += $i)
                $isPrime[$j] = false;
        }
    }
 
    // Forming array of the
    // prime numbers found
    $primes = array();
    $k = 0;
    for ($i = 2; $i <= $n; $i++)
        if ($isPrime[$i])
            $primes[$k++]=$i;
    return $primes;
}
 
// Checking whether a
// number is k-rough or not
function isRough($n, $k)
{
    $primes = getPrimes($n);
 
    // Finding minimum
    // prime factor of n
    $min_pf = $n;
    for ($i = 0;
         $i < count($primes); $i++)
        if ($n % $primes[$i] == 0)
            $min_pf = $primes[$i];
 
    // Return true if minimum
    // prime factor is greater
    // than or equal to k. Else
    // return false.
    return ($min_pf >= $k);
}
 
// Driver Code
$n = 75;
$k = 3;
if (isRough($n, $k))
    echo $n . " is a " .
         $k . "-rough number\n";
else
    echo $n . " is not a " .
         $k . "-rough number\n";
          
// This code is contributed by mits
?>

<script>
 
// Javascript to check if n is a k-rough number
// or not
 
// Finds primes by Sieve of Eratosthenes
// method
function getPrimes(n)
{
    var i, j;
    var isPrime = Array(n+1).fill(true);
    for (i = 2; i * i <= n; i++)
    {
 
        // If isPrime[i] is not changed,
        // then it is prime
        if (isPrime[i] == true)
        {
            // Update all multiples of p
            for (j = i * 2; j <= n; j += i)
                isPrime[j] = false;
        }
    }
 
    // Forming array of the prime numbers found
    var primes = [];
    for (i = 2; i <= n; i++)
        if (isPrime[i])
            primes.push(i);
    return primes;
}
 
// Checking whether a number is k-rough or not
function isRough(n, k)
{
    var primes = getPrimes(n);
 
    // Finding minimum prime factor of n
    var min_pf = n;
    for (var i = 0; i < primes.length; i++)
        if (n % primes[i] == 0)
            min_pf = primes[i];
 
    // Return true if minimum prime factor
    // is greater than or equal to k. Else
    // return false.
    return (min_pf >= k);
}
 
// Driver Method
var n = 75, k = 3;
if (isRough(n, k))
    document.write( n + " is a "
        + k + "-rough number<br>");
else
    document.write( n + " is not a "
        + k + "-rough number<br>");
 
// This code is contributed by itsok.
</script>

Producción: 
 

75 is a 3-rough number

Complejidad de Tiempo: O(√n log n) 
Espacio Auxiliar: O(n)
 

Solución eficiente:

La idea se basa en un programa eficiente para imprimir todos los factores primos de un número dado . 
 

1. Si n es divisible por 2 (el número primo más pequeño), devolvemos verdadero si k es menor o igual a 2. De lo contrario, devolvemos falso.
2. Luego probamos uno por uno todos los números impares. Tan pronto como encontramos un número impar que divide a n, lo comparamos con k y devolvemos verdadero si el número impar es mayor o igual que k, de lo contrario falso. Esta solución funciona porque si un número primo no divide a n, sus múltiplos tampoco lo harán.

// CPP program to check if given n is
// k-rough or not.
# include <bits/stdc++.h>
using namespace std;
 
// Returns true if n is k rough else false
bool isKRough(int n, int k)
{
    // If n is even, then smallest prime
    // factor becomes 2.
    if (n % 2 == 0)
        return (k <= 2);
 
    // n must be odd at this point.  So we
    // can skip one element (Note i = i +2)
    for (int i = 3; i*i <= n; i = i+2)
        if (n%i == 0)
            return (i >= k);
 
   return (n >= k);
}
 
/* Driver program to test above function */
int main()
{
    int n = 75, k = 3;
    if (isKRough(n, k))
        cout << n << " is a "
             << k << "-rough number\n";
    else
        cout << n << " is not a "
             << k << "-rough number\n";
    return 0;
}

// Java program to check if given n is
// k-rough or not.
 
class GFG {
     
// Returns true if n is k rough else false
static boolean isKRough(int n, int k)
{
    // If n is even, then smallest
    // prime factor becomes 2.
    if (n % 2 == 0)
        return (k <= 2);
 
    // n must be odd at this point. So we
    // can skip one element (Note i = i + 2)
    for (int i = 3; i*i <= n; i = i + 2)
        if (n % i == 0)
            return (i >= k);
 
return (n >= k);
}
 
/* Driver program to test above function */
public static void main(String[] args)
{
    int n = 75, k = 3;
    if (isKRough(n, k))
        System.out.println(n + " is a " +
                     k + "-rough number");
    else
        System.out.println(n + " is not a " +
                        k + "-rough number");
}
}
 
// This code is contributed by Smitha

# Python3 program to check if given n
# is k-rough or not.
 
# Returns true if n is k rough else false
def isKRough(n, k):
     
    # If n is even, then smallest
    # prime factor becomes 2.
    if(n % 2 == 0):
        return (k <= 2);
         
    # n must be odd at this point.
    # So we can skip one element
    # (Note i = i +2)
    i = 3;
    while(i * i <= n):
        if(n % i == 0):
            return (i >= k);
        i = i + 2;
     
    return (n >= k);
 
# Driver Code
n = 75;
k = 3;
if (isKRough(n, k)):
    print(n, "is a", k, "-rough number");
else:
    print(n, "is not a", k, "-rough number");
     
# This code is contributed by mits

// C# program to check if given n is
// k-rough or not.
using System;
 
class GFG {
     
// Returns true if n is k rough else false
static bool isKRough(int n, int k)
{
    // If n is even, then smallest prime
    // factor becomes 2.
    if (n % 2 == 0)
        return (k <= 2);
 
    // n must be odd at this point. So we
    // can skip one element (Note i = i + 2)
    for (int i = 3; i*i <= n; i = i + 2)
        if (n % i == 0)
            return (i >= k);
 
return (n >= k);
}
 
/* Driver program to test above function */
public static void Main()
{
    int n = 75, k = 3;
    if (isKRough(n, k))
        Console.Write(n + " is a " +
             k + "-rough number\n");
    else
        Console.Write(n + " is not a " +
                 k + "-rough number\n");
}
}
 
// This code is contributed by Smitha

<?php
// PHP program to check if
// given n is k-rough or not.
 
// Returns true if n is k
// rough else false
function isKRough($n, $k)
{
    // If n is even, then smallest
    // prime factor becomes 2.
    if ($n % 2 == 0)
        return ($k <= 2);
 
    // n must be odd at this point.
    // So we can skip one element
    // (Note i = i +2)
    for ($i = 3; $i * $i <= $n; $i = $i + 2)
        if ($n % $i == 0)
            return ($i >= $k);
 
return ($n >= $k);
}
 
// Driver Code
$n = 75;
$k = 3;
if (isKRough($n, $k))
    echo $n . " is a " . $k .
           "-rough number\n";
else
    echo $n . " is not a " . $k .
               "-rough number\n";
     
// This code is contributed by Sam007
?>

<script>
// Javascript program to check if
// given n is k-rough or not.
 
// Returns true if n is k
// rough else false
function isKRough(n, k)
{
 
    // If n is even, then smallest
    // prime factor becomes 2.
    if (n % 2 == 0)
        return (k <= 2);
 
    // n must be odd at this point.
    // So we can skip one element
    // (Note i = i +2)
    for (let i = 3; i * i <= n; i = i + 2)
        if (n % i == 0)
            return (i >= k);
 
return (n >= k);
}
 
// Driver Code
let n = 75;
let k = 3;
if (isKRough(n, k))
    document.write( n + " is a " + k + "-rough number<br>");
else
    document.write( n + " is not a " + k + "-rough number<br>");
     
// This code is contributed by sravan kumar
</script>

Producción : 
 

75 is a 3-rough number

Complejidad temporal : O(√n) 
Espacio auxiliar: O(1)

Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.