Dado un entero X , denota el número de factores que puede tener un entero positivo N. La tarea es encontrar el número máximo de factores primos distintos que puede tener el número N.
Ejemplos:
Entrada: X = 9
Salida : 2
Explicación:
Algunos de los números posibles que tienen 9 factores son:
256: 1, 2 , 4, 8, 16, 32, 64, 128, 256
Número de factores primos = 1
36: 1, 2 , 3 , 4, 6, 9, 12, 18, 36
Número de factores primos = 2Entrada: X = 8
Salida: 3
Algunos de los números que tienen 8 factores son:
128 : 1, 2, 4, 8, 16, 32, 64, 128
Número de factores primos = 1
24 : 1, 2, 3, 4, 6, 8, 12, 24
Número de factores primos = 2
30 : 1, 2, 3, 5 , 6, 10, 15, 30
Número de factores primos = 3
Enfoque: La observación clave en el problema es que cualquier número natural positivo se puede representar como producto de sus factores primos de la siguiente manera:
// Number can be represented as product // prime factors as follows// Total number of factors of N can be // defined as follows Number of Factors = (p+1) * (q+1) * (r+1)..
En el problema anterior, se proporciona la cantidad de factores que se pueden usar para encontrar la máxima cantidad de factores primos posibles para un número con la cantidad de factores dada de la siguiente manera:
If X can be expressed as product of K numbers then we have at most K primes in X. In Order to split X as product of maximum number of values, all the values should be prime. X = (p+1) * (q+1) * (r+1) // So the maximum number of prime // factors of the given number greater // than 1 can lead to a number N. Let's say X = 12 X = 2 * 2 * 3 Then possible N can be: N = a(2-1) * b(2-1) * c(3-1) N = a1 * b1 * c2 // Here a, b, and c can be any distinct prime // numbers to get the possible value of N N = 21 * 31 * 52 N = 150 let's say X = 8 X = 2 * 2 * 2 N = 21 * 31 * 51 N = 30
Por lo tanto, la cuenta máxima de divisores primos de un número que puede tener es la cuenta de los factores primos (pueden ser repetitivos también) en la factorización de la cuenta de factores del número.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// maximum count of the prime factors
// by the count of factors of number
#include <iostream>
#include <math.h>
using namespace std;
// Function to count number
// of prime factors of x
int countPrimeFactors(int n)
{
if (n == 1)
return 0;
// Count variable is
// incremented for every
// prime factor of x
int cnt = 0;
while (n % 2 == 0) {
cnt++;
n = n / 2;
}
// Loop to count the number
// of the prime factors of
// the given number
for (int i = 3; i <= sqrt(n);
i += 2) {
while (n % i == 0) {
cnt++;
n = n / i;
}
}
if (n > 2)
cnt++;
return cnt;
}
// Driver Code
int main()
{
int x = 8;
int prime_factor_cnt = countPrimeFactors(x);
cout << prime_factor_cnt << endl;
return 0;
}
Java
// Java implementation to find the
// maximum count of the prime factors
// by the count of factors of number
class GFG {
// Function to count number
// of prime factors of x
static int countPrimeFactors(int n)
{
if (n == 1)
return 0;
// Count variable is
// incremented form every
// prime factor of x
int cnt = 0;
while (n % 2 == 0) {
cnt++;
n = n / 2;
}
// Loop to count the number
// of the prime factors of
// the given number
for (int i = 3; i <= Math.sqrt(n); i += 2) {
while (n % i == 0) {
cnt++;
n = n / i;
}
}
if (n > 2)
cnt++;
return cnt;
}
// Driver Code
public static void main(String[] args)
{
int x = 8;
int prime_factor_cnt = countPrimeFactors(x);
System.out.print(prime_factor_cnt + "\n");
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation to find the # maximum count of the prime factors # by the count of factors of number import math # Function to count number # of prime factors of x def countPrimeFactors(n): if (n == 1): return 0 # Count variable is # incremented form every # prime factor of x cnt = 0 while (n % 2 == 0): cnt += 1 n = n // 2 # Loop to count the number # of the prime factors of # the given number for i in range(3, int(math.sqrt(n)) + 1, 2): while (n % i == 0): cnt += 1 n = n // i if (n > 2): cnt += 1 return cnt # Driver Code x = 8 prime_factor_cnt = countPrimeFactors(x) print(prime_factor_cnt) # This code is contributed by ShubhamCoder
C#
// C# implementation to find the
// maximum count of the prime factors
// by the count of factors of number
using System;
class GFG {
// Function to count number
// of prime factors of x
static int countPrimeFactors(int n)
{
if (n == 1)
return 0;
// Count variable is
// incremented form every
// prime factor of x
int cnt = 0;
while (n % 2 == 0) {
cnt++;
n = n / 2;
}
// Loop to count the number
// of the prime factors of
// the given number
for (int i = 3;
i <= Math.Sqrt(n); i += 2) {
while (n % i == 0) {
cnt++;
n = n / i;
}
}
if (n > 2)
cnt++;
return cnt;
}
// Driver Code
static public void Main()
{
int x = 8;
int prime_factor_cnt = countPrimeFactors(x);
Console.Write(prime_factor_cnt);
}
}
// This code is contributed by ShubhamCoder
Javascript
<script>
// Javascript implementation to find the
// maximum count of the prime factors
// by the count of factors of number
// Function to count number
// of prime factors of x
function countPrimeFactors(n)
{
if (n == 1)
return 0;
// Count variable is
// incremented for every
// prime factor of x
let cnt = 0;
while (n % 2 == 0)
{
cnt++;
n = parseInt(n / 2);
}
// Loop to count the number
// of the prime factors of
// the given number
for(let i = 3; i <= Math.sqrt(n); i += 2)
{
while (n % i == 0)
{
cnt++;
n = parseInt(n / i);
}
}
if (n > 2)
cnt++;
return cnt;
}
// Driver Code
let x = 8;
let prime_factor_cnt = countPrimeFactors(x);
document.write(prime_factor_cnt);
// This code is contributed by souravmahato348
</script>
3
Complejidad de tiempo: O(N 1/2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por aishwary191 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA