Dado un número n, necesitamos encontrar el producto de todos sus factores primos únicos. Factores primos: Es básicamente un factor del número que es un número primo en sí mismo.
Ejemplos:
Input: num = 10 Output: Product is 10 Explanation: Here, the input number is 10 having only 2 prime factors and they are 5 and 2. And hence their product is 10. Input : num = 25 Output: Product is 5 Explanation: Here, for the input to be 25 we have only one unique prime factor i.e 5. And hence the required product is 5.
Método 1 (Simple)
Usar un ciclo de i = 2 a n y verificar si i es un factor de n, luego verificar si i es un número primo, si es así, luego almacenar el producto en la variable del producto y continuar este proceso hasta i = n.
CPP
// C++ program to find product of
// unique prime factors of a number
#include <bits/stdc++.h>
using namespace std;
long long int productPrimeFactors(int n)
{
long long int product = 1;
for (int i = 2; i <= n; i++) {
// Checking if 'i' is factor of num
if (n % i == 0) {
// Checking if 'i' is a Prime number
bool isPrime = true;
for (int j = 2; j <= i / 2; j++) {
if (i % j == 0) {
isPrime = false;
break;
}
}
// condition if 'i' is Prime number
// as well as factor of num
if (isPrime) {
product = product * i;
}
}
}
return product;
}
// driver function
int main()
{
int n = 44;
cout << productPrimeFactors(n);
return 0;
}
Java
// Java program to find product of
// unique prime factors of a number.
class GFG {
public static long productPrimeFactors(int n)
{
long product = 1;
for (int i = 2; i <= n; i++) {
// Checking if 'i' is factor of num
if (n % i == 0) {
// Checking if 'i' is a Prime number
boolean isPrime = true;
for (int j = 2; j <= i / 2; j++) {
if (i % j == 0) {
isPrime = false;
break;
}
}
// condition if 'i' is Prime number
// as well as factor of num
if (isPrime) {
product = product * i;
}
}
}
return product;
}
// Driver Code
public static void main(String[] args)
{
int n = 44;
System.out.print(productPrimeFactors(n));
}
}
// This code is contributed by _omg
Python3
# Python program to find sum of given # series. def productPrimeFactors(n): product = 1 for i in range(2, n + 1): if (n % i == 0): isPrime = 1 for j in range(2, int(i / 2 + 1)): if (i % j == 0): isPrime = 0 break # condition if 'i' is Prime number # as well as factor of num if (isPrime): product = product * i return product # main() n = 44 print (productPrimeFactors(n)) # Contributed by _omg
C#
// C# program to find product of
// unique prime factors of a number.
using System;
class GFG {
// Function to find product of unique
// prime factors of a number
public static long productPrimeFactors(int n)
{
long product = 1;
for (int i = 2; i <= n; i++) {
// Checking if 'i' is factor of num
if (n % i == 0) {
// Checking if 'i' is a Prime number
bool isPrime = true;
for (int j = 2; j <= i / 2; j++) {
if (i % j == 0) {
isPrime = false;
break;
}
}
// condition if 'i' is Prime number
// as well as factor of num
if (isPrime) {
product = product * i;
}
}
}
return product;
}
// Driver Code
public static void Main()
{
int n = 44;
Console.Write(productPrimeFactors(n));
}
}
// This code is contributed by nitin mittal
PHP
<?php
// PHP program to find
// product of unique
// prime factors of a number
function productPrimeFactors($n)
{
$product = 1;
for ($i = 2; $i <= $n; $i++)
{
// Checking if 'i' is
// factor of num
if ($n % $i == 0)
{
// Checking if 'i' is
// a Prime number
$isPrime = true;
for ($j = 2; $j <= $i / 2; $j++)
{
if ($i % $j == 0)
{
$isPrime = false;
break;
}
}
// condition if 'i' is
// Prime number as well
// as factor of num
if ($isPrime)
{
$product = $product * $i;
}
}
}
return $product;
}
// Driver Code
$n = 44;
echo(productPrimeFactors($n));
// This code is contributed by Ajit.
?>
Javascript
<script>
// JavaScript program to find product of
// unique prime factors of a number.
function productPrimeFactors(n)
{
let product = 1;
for (let i = 2; i <= n; i++) {
// Checking if 'i' is factor of num
if (n % i == 0) {
// Checking if 'i' is a Prime number
let isPrime = true;
for (let j = 2; j <= i / 2; j++) {
if (i % j == 0) {
isPrime = false;
break;
}
}
// condition if 'i' is Prime number
// as well as factor of num
if (isPrime) {
product = product * i;
}
}
}
return product;
}
// Driver Code
let n = 44;
document.write(productPrimeFactors(n));
// This code is contributed by avijitmondal1998.
</script>
Producción :
22
Tiempo Complejidad: O(n 2 )
Espacio Auxiliar: O(1)
Método 2 (Eficiente)
La idea se basa en el programa Eficiente para imprimir todos los factores primos de un número dado
CPP
// C++ program to find product of
// unique prime factors of a number
#include <bits/stdc++.h>
using namespace std;
// A function to print all prime
// factors of a given number n
long long int productPrimeFactors(int n)
{
long long int product = 1;
// Handle prime factor 2 explicitly
// so that can optimally handle
// other prime factors.
if (n % 2 == 0) {
product *= 2;
while (n % 2 == 0)
n = n / 2;
}
// n must be odd at this point.
// So we can skip one element
// (Note i = i + 2)
for (int i = 3; i <= sqrt(n); i = i + 2) {
// While i divides n, print
// i and divide n
if (n % i == 0) {
product = product * i;
while (n % i == 0)
n = n / i;
}
}
// This condition is to handle the
// case when n is a prime number
// greater than 2
if (n > 2)
product = product * n;
return product;
}
// Driver Code
int main()
{
int n = 44;
cout << productPrimeFactors(n);
return 0;
}
Java
// Java program to find product of
// unique prime factors of a number.
import java.util.*;
import java.lang.*;
class GFG {
public static long productPrimeFactors(int n)
{
long product = 1;
// Handle prime factor 2
// explicitly so that can
// optimally handle other
// prime factors.
if (n % 2 == 0) {
product *= 2;
while (n % 2 == 0)
n = n / 2;
}
// n must be odd at this point.
// So we can skip one element
// (Note i = i +2)
for (int i = 3; i <= Math.sqrt(n); i = i + 2) {
// While i divides n, print
// i and divide n
if (n % i == 0) {
product = product * i;
while (n % i == 0)
n = n / i;
}
}
// This condition is to handle
// the case when n is a prime
// number greater than 2
if (n > 2)
product = product * n;
return product;
}
// Driver Code
public static void main(String[] args)
{
int n = 44;
System.out.print(productPrimeFactors(n));
}
}
// This code is contributed by _omg
Python3
# Python program to find product of # unique prime factors of a number import math def productPrimeFactors(n): product = 1 # Handle prime factor 2 explicitly so that # can optimally handle other prime factors. if (n % 2 == 0): product *= 2 while (n % 2 == 0): n = n / 2 # n must be odd at this point. So we can # skip one element (Note i = i + 2) for i in range (3, int(math.sqrt(n))+1, 2): # While i divides n, print i and # divide n if (n % i == 0): product = product * i while (n % i == 0): n = n / i # This condition is to handle the case when n # is a prime number greater than 2 if (n > 2): product = product * n return product # main() n = 44 print (int(productPrimeFactors(n))) # Contributed by _omg
C#
// C# program to find product
// of unique prime factors
// of a number.
using System;
public class GFG {
// Function to find product
// of prime factors
public static long productPrimeFactors(int n)
{
long product = 1;
// Handle prime factor 2 explicitly
// so that can optimally handle
// other prime factors.
if (n % 2 == 0) {
product *= 2;
while (n % 2 == 0)
n = n / 2;
}
// n must be odd at this point.
// So we can skip one
// element (Note i = i + 2)
for (int i = 3; i <= Math.Sqrt(n);
i = i + 2) {
// While i divides n, print
// i and divide n
if (n % i == 0) {
product = product * i;
while (n % i == 0)
n = n / i;
}
}
// This condition is to handle
// the case when n is a prime
// number greater than 2
if (n > 2)
product = product * n;
return product;
}
// Driver Code
public static void Main(String[] args)
{
int n = 44;
Console.Write(productPrimeFactors(n));
}
}
// This code is contributed by parashar...
PHP
<?php
// PHP program to find product of
// unique prime factors of a number
// A function to print all prime
// factors of a given number n
function productPrimeFactors( $n)
{
$product = 1;
// Handle prime factor 2
// explicitly so that can
// optimally handle other
// prime factors.
if ($n % 2 == 0)
{
$product *= 2;
while ($n % 2 == 0)
$n = $n / 2;
}
// n must be odd at this point.
// So we can skip one element
// (Note i = i + 2)
for ($i = 3; $i <= sqrt($n); $i = $i + 2)
{
// While i divides n, print
// i and divide n
if ($n % $i == 0)
{
$product = $product * $i;
while ($n % $i == 0)
$n = $n / $i;
}
}
// This condition is to handle the
// case when n is a prime number
// greater than 2
if ($n > 2)
$product = $product * $n;
return $product;
}
// Driver Code
$n = 44;
echo productPrimeFactors($n);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find product of
// unique prime factors of a number.
function productPrimeFactors(n)
{
var product = 1;
// Handle prime factor 2
// explicitly so that can
// optimally handle other
// prime factors.
if (n % 2 == 0) {
product *= 2;
while (n % 2 == 0)
n = n / 2;
}
// n must be odd at this point.
// So we can skip one element
// (Note i = i +2)
for (i = 3; i <= Math.sqrt(n); i = i + 2)
{
// While i divides n, print
// i and divide n
if (n % i == 0) {
product = product * i;
while (n % i == 0)
n = n / i;
}
}
// This condition is to handle
// the case when n is a prime
// number greater than 2
if (n > 2)
product = product * n;
return product;
}
// Driver Code
var n = 44;
document.write(productPrimeFactors(n));
// This code contributed by aashish1995
</script>
Producción :
22
Complejidad de Tiempo: O(√n log 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.
Publicación traducida automáticamente
Artículo escrito por Archit18_PEC y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA