Dado un número no negativo n . El problema es verificar si el número dado n puede expresarse como un producto de números de un solo dígito o no.
Ejemplos:
Input : n = 24 Output : Yes Different combinations are: (8*3) and (6*4) Input : 68 Output : No To represent 68 as product of number, 17 must be included which is a two digit number.
Planteamiento: Tenemos que comprobar si el número n no tiene factores primos distintos de 2, 3, 5, 7 . Para esto, dividimos repetidamente el número n entre (2, 3, 5, 7) hasta que ya no se puede dividir entre estos números. Después de este proceso, si n == 1, entonces se puede expresar como un producto de números de un solo dígito; de lo contrario, si es mayor que 1, entonces no se puede expresar.
C++
// C++ implementation to check whether a number can be
// expressed as a product of single digit numbers
#include <bits/stdc++.h>
using namespace std;
// Number of single digit prime numbers
#define SIZE 4
// function to check whether a number can be
// expressed as a product of single digit numbers
bool productOfSingelDgt(int n)
{
// if 'n' is a single digit number, then
// it can be expressed
if (n >= 0 && n <= 9)
return true;
// define single digit prime numbers array
int prime[] = { 2, 3, 5, 7 };
// repeatedly divide 'n' by the given prime
// numbers until all the numbers are used
// or 'n' > 1
for (int i = 0; i < SIZE && n > 1; i++)
while (n % prime[i] == 0)
n = n / prime[i];
// if true, then 'n' can
// be expressed
return (n == 1);
}
// Driver program to test above
int main()
{
int n = 24;
productOfSingelDgt(n)? cout << "Yes" :
cout << "No";
return 0;
}
Java
// Java implementation to check whether
// a number can be expressed as a
// product of single digit numbers
import java.util.*;
class GFG
{
// Number of single digit prime numbers
static int SIZE = 4;
// function to check whether a number can
// be expressed as a product of single
// digit numbers
static boolean productOfSingelDgt(int n)
{
// if 'n' is a single digit number,
// then it can be expressed
if (n >= 0 && n <= 9)
return true;
// define single digit prime numbers
// array
int[] prime = { 2, 3, 5, 7 };
// repeatedly divide 'n' by the given
// prime numbers until all the numbers
// are used or 'n' > 1
for (int i = 0; i < SIZE && n > 1; i++)
while (n % prime[i] == 0)
n = n / prime[i];
// if true, then 'n' can
// be expressed
return (n == 1);
}
// Driver program to test above
public static void main (String[] args)
{
int n = 24;
if(productOfSingelDgt(n))
System.out.println("Yes");
else
System.out.println("No");
}
}
/* This code is contributed by Mr. Somesh Awasthi */
Python3
# Python3 program to check
# whether a number can be
# expressed as a product of
# single digit numbers
# Number of single digit
# prime numbers
SIZE = 4
# function to check whether
# a number can be
# expressed as a product
# of single digit numbers
def productOfSingelDgt(n):
# if 'n' is a single digit
# number, then
# it can be expressed
if n >= 0 and n <= 9:
return True
# define single digit prime
# numbers array
prime = [ 2, 3, 5, 7 ]
# repeatedly divide 'n' by
# the given prime
# numbers until all the
# numbers are used
# or 'n' > 1
i = 0
while i < SIZE and n > 1:
while n % prime[i] == 0:
n = n / prime[i]
i += 1
# if true, then 'n' can
# be expressed
return n == 1
n = 24
if productOfSingelDgt(n):
print ("Yes")
else :
print ("No")
# This code is contributed
# by Shreyanshi Arun.
C#
// C# implementation to check whether
// a number can be expressed as a
// product of single digit numbers
using System;
class GFG {
// Number of single digit prime numbers
static int SIZE = 4;
// function to check whether a number can
// be expressed as a product of single
// digit numbers
static bool productOfSingelDgt(int n)
{
// if 'n' is a single digit number,
// then it can be expressed
if (n >= 0 && n <= 9)
return true;
// define single digit prime numbers
// array
int[] prime = { 2, 3, 5, 7 };
// repeatedly divide 'n' by the given
// prime numbers until all the numbers
// are used or 'n' > 1
for (int i = 0; i < SIZE && n > 1; i++)
while (n % prime[i] == 0)
n = n / prime[i];
// if true, then 'n' can
// be expressed
return (n == 1);
}
// Driver program to test above
public static void Main()
{
int n = 24;
if (productOfSingelDgt(n))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP implementation to check
// whether a number can be
// expressed as a product of
// single digit numbers
// function to check whether
// a number can be expressed
//as a product of single
// digit numbers
function productOfSingelDgt($n,$SIZE)
{
// if 'n' is a single
// digit number, then
// it can be expressed
if ($n >= 0 && $n <= 9)
return true;
// define single digit
// prime numbers array
$prime = array(2, 3, 5, 7);
// repeatedly divide 'n'
// by the given prime
// numbers until all
// the numbers are used
// or 'n' > 1
for ($i = 0; $i < $SIZE && $n > 1; $i++)
while ($n % $prime[$i] == 0)
$n = $n / $prime[$i];
// if true, then 'n' can
// be expressed
return ($n == 1);
}
// Driver Code
$SIZE = 4;
$n = 24;
if(productOfSingelDgt($n, $SIZE))
echo "Yes" ;
else
echo "No";
// This code is contributed by Sam007
?>
Javascript
<script>
// javascript implementation to check whether
// a number can be expressed as a
// product of single digit numbers
// Number of single digit prime numbers
const SIZE = 4;
// function to check whether a number can
// be expressed as a product of single
// digit numbers
function productOfSingelDgt(n)
{
// if 'n' is a single digit number,
// then it can be expressed
if (n >= 0 && n <= 9)
return true;
// define single digit prime numbers
// array
var prime = [ 2, 3, 5, 7 ];
// repeatedly divide 'n' by the given
// prime numbers until all the numbers
// are used or 'n' > 1
for (i = 0; i < SIZE && n > 1; i++)
while (n % prime[i] == 0)
n = n / prime[i];
// if true, then 'n' can
// be expressed
return (n == 1);
}
// Driver program to test above
var n = 24;
if (productOfSingelDgt(n))
document.write("Yes");
else
document.write("No");
// This code is contributed by gauravrajput1
</script>
Producción:
Yes
Complejidad temporal: O(num), donde num es el número de factores primos (2, 3, 5, 7) de n .
Este artículo es una contribución de Ayush Jauhari . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA