Un número P-suave o P-friable es un número entero cuyo factor primo más grande es menor o igual que P. Dados N y P, necesitamos escribir un programa para comprobar si es P-friable o no.
Ejemplos:
Input : N = 24 , P = 7
Output : YES
Explanation : The prime divisors of 24 are 2 and 3 only.
Hence its largest prime factor is 3 which
is less than or equal to 7, it is P-friable.
Input : N = 22 , P = 5
Output : NO
Explanation : The prime divisors are 11 and 2, hence 11>5,
so it is not a P-friable number.
El enfoque será convertir en factores primos el número y almacenar el máximo de todos los factores primos. Primero dividimos el número por 2 si es divisible, luego iteramos de 3 a Sqrt(n) para obtener el número de veces que un número primo divide a un número particular que se reduce cada vez por n/i y almacenamos el factor primo i si divide a N. Dividimos nuestro número n (por factores primos) por su factor primo más pequeño correspondiente hasta que n se convierte en 1. Y si al final n > 2, significa que es un número primo, así que lo almacenamos como factor primo como bien. Al final, el factor más grande se compara con p para comprobar si es un número p-suave o no.
C++
// CPP program to check if a number is
// a p-smooth number or not
#include <iostream>
#include<math.h>
using namespace std;
// function to check if number n
// is a P-smooth number or not
bool check(int n, int p)
{
int maximum = -1;
// prime factorise it by 2
while (!(n % 2))
{
// if the number is divisible by 2
maximum = max(maximum, 2);
n = n/2;
}
// check for all the possible numbers
// that can divide it
for (int i = 3; i <= sqrt(n); i += 2)
{
// prime factorize it by i
while (n % i == 0)
{
// stores the maximum if maximum
// and i, if i divides the number
maximum = max(maximum,i);
n = n / i;
}
}
// if n at the end is a prime number,
// then it a divisor itself
if (n > 2)
maximum = max(maximum, n);
return (maximum <= p);
}
// Driver program to test above function
int main()
{
int n = 24, p = 7;
if (check(n, p))
cout << "yes";
else
cout << "no";
return 0;
}
Java
// Java program to check if a number is
// a p-smooth number or not
import java.lang.*;
class GFG{
// function to check if number n
// is a P-smooth number or not
static boolean check(int n, int p)
{
int maximum = -1;
// prime factorise it by 2
while ((n % 2) == 0)
{
// if the number is divisible by 2
maximum = Math.max(maximum, 2);
n = n/2;
}
// check for all the possible numbers
// that can divide it
for (int i = 3; i <= Math.sqrt(n); i += 2)
{
// prime factorize it by i
while (n % i == 0)
{
// stores the maximum if maximum
// and i, if i divides the number
maximum = Math.max(maximum,i);
n = n / i;
}
}
// if n at the end is a prime number,
// then it a divisor itself
if (n > 2)
maximum = Math.max(maximum, n);
return (maximum <= p);
}
// Driver program to test
// above function
public static void main(String[] args)
{
int n = 24, p = 7;
if (check(n, p))
System.out.println("yes");
else
System.out.println("no");
}
}
// This code is contributed by
// Smitha Dinesh Semwal
Python3
# Python 3 program to # check if a number is # a p-smooth number or not import math # function to check if number n # is a P-smooth number or not def check(n, p) : maximum = -1 # prime factorise it by 2 while (not(n % 2)): # if the number is divisible by 2 maximum = max(maximum, 2) n = int(n/2) # check for all the possible numbers # that can divide it for i in range(3,int(math.sqrt(n)), 2): # prime factorize it by i while (n % i == 0) : # stores the maximum if maximum # and i, if i divides the number maximum = max(maximum,i) n = int(n / i) # if n at the end is a prime number, # then it a divisor itself if (n > 2): maximum = max(maximum, n) return (maximum <= p) # Driver program to test above function n = 24 p = 7 if (check(n, p)): print( "yes" ) else: print( "no" ) # This code is contributed by # Smitha Dinesh Semwal
C#
// C# program to check if a number is
// a p-smooth number or not
using System;
class GFG {
// function to check if number n
// is a P-smooth number or not
static bool check(int n, int p)
{
int maximum = -1;
// prime factorise it by 2
while ((n % 2) == 0)
{
// if the number is divisible by 2
maximum = Math.Max(maximum, 2);
n = n / 2;
}
// check for all the possible numbers
// that can divide it
for (int i = 3; i <= Math.Sqrt(n); i += 2)
{
// prime factorize it by i
while (n % i == 0)
{
// stores the maximum if maximum
// and i, if i divides the number
maximum = Math.Max(maximum, i);
n = n / i;
}
}
// if n at the end is a prime number,
// then it a divisor itself
if (n > 2)
maximum = Math.Max(maximum, n);
return (maximum <= p);
}
// Driver program to test
// above function
public static void Main()
{
int n = 24, p = 7;
if (check(n, p))
Console.Write("yes");
else
Console.Write("no");
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to check if a number is
// a p-smooth number or not
// function to check if number n
// is a P-smooth number or not
function check($n, $p)
{
$maximum = -1;
// prime factorise it by 2
while (!($n % 2))
{
// if the number is
// divisible by 2
$maximum = max($maximum, 2);
$n = $n / 2;
}
// check for all the possible
// numbers that can divide it
for ($i = 3; $i <= sqrt($n); $i += 2)
{
// prime factorize it by i
while ($n % $i == 0)
{
// stores the maximum if maximum
// and i, if i divides the number
$maximum = max($maximum, $i);
$n = $n / $i;
}
}
// if n at the end is a prime number,
// then it a divisor itself
if ($n > 2)
$maximum = max($maximum, $n);
return ($maximum <= $p);
}
// Driver Code
$n = 24; $p = 7;
if (check($n, $p))
echo("yes");
else
echo("no");
// This code is contributed by Ajit.
?>
Javascript
<script>
// Javascript program to check if a number is
// a p-smooth number or not
// function to check if number n
// is a P-smooth number or not
function check(n, p)
{
let maximum = -1;
// prime factorise it by 2
while (!(n % 2))
{
// if the number is divisible by 2
maximum = Math.max(maximum, 2)
n = n/2;
}
// check for all the possible numbers
// that can divide it
var i;
for (i = 3; i*i <= n; i += 2)
{
// prime factorize it by i
while (n % i == 0)
{
// stores the maximum if maximum
// and i, if i divides the number
maximum = Math.max(maximum, i);
n = n / i;
}
}
// if n at the end is a prime number,
// then it a divisor itself
if (n > 2)
maximum = Math.max(maximum, n);
if (maximum <= p)
return true;
else
return false;
}
// Driver Code
let n = 24, p = 7;
if (check(n, p))
document.write("yes");
else
document.write("no");
// This code is contributed by ajaykrsharma132.
</script>
Producción:
yes
Complejidad de tiempo : O (sqrt (N) * logN), ya que estamos usando bucles anidados para atravesar sqrt (N) * logN veces.
Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.
Referencia :
http://oeis.org/wiki/P-smooth_numbers