Dados tres números enteros L , R y P donde P es primo, la tarea es contar el número de veces que P ocurre en la descomposición en factores primos de todos los números en el rango [L, R] .
Ejemplos:
Entrada: L = 2, R = 8, P = 2
Salida: 7
Elemento factores primos Ocurre el tiempo 2 2 2 1 3 3 0 4 2 * 2 2 5 5 0 6 2 * 3 1 7 7 0 8 2 * 2 * 2 3 1 + 0 + 2 + 0 + 1 + 0 + 3 = 7
Entrada: L = 5, R = 25, P = 7
Salida: 3
Enfoque ingenuo: simplemente iterar sobre el rango y para cada valor contar cuántas veces P divide ese valor y sumarlos para obtener el resultado. Complejidad temporal O(R – L) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
// Function to return the highest
// power of p that divides n
int countFactors(int n, int p)
{
int pwr = 0;
while (n > 0 && n % p == 0) {
n /= p;
pwr++;
}
return pwr;
}
// Function to return the count of times p
// appears in the prime factors of the
// elements from the range [l, r]
int getCount(int l, int r, int p)
{
// To store the required count
int cnt = 0;
// For every element of the range
for (int i = l; i <= r; i++) {
// Add the highest power of
// p that divides i
cnt += countFactors(i, p);
}
return cnt;
}
// Driver code
int main()
{
int l = 2, r = 8, p = 2;
cout << getCount(l, r, p);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the highest
// power of p that divides n
static int countFactors(int n, int p)
{
int pwr = 0;
while (n > 0 && n % p == 0)
{
n /= p;
pwr++;
}
return pwr;
}
// Function to return the count of times p
// appears in the prime factors of the
// elements from the range [l, r]
static int getCount(int l, int r, int p)
{
// To store the required count
int cnt = 0;
// For every element of the range
for (int i = l; i <= r; i++)
{
// Add the highest power of
// p that divides i
cnt += countFactors(i, p);
}
return cnt;
}
// Driver code
public static void main(String[] args)
{
int l = 2, r = 8, p = 2;
System.out.println(getCount(l, r, p));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach # Function to return the highest # power of p that divides n def countFactors(n, p) : pwr = 0; while (n > 0 and n % p == 0) : n //= p; pwr += 1; return pwr; # Function to return the count of times p # appears in the prime factors of the # elements from the range [l, r] def getCount(l, r, p) : # To store the required count cnt = 0; # For every element of the range for i in range(l, r + 1) : # Add the highest power of # p that divides i cnt += countFactors(i, p); return cnt; # Driver code if __name__ == "__main__" : l = 2; r = 8; p = 2; print(getCount(l, r, p)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the highest
// power of p that divides n
static int countFactors(int n, int p)
{
int pwr = 0;
while (n > 0 && n % p == 0)
{
n /= p;
pwr++;
}
return pwr;
}
// Function to return the count of times p
// appears in the prime factors of the
// elements from the range [l, r]
static int getCount(int l, int r, int p)
{
// To store the required count
int cnt = 0;
// For every element of the range
for (int i = l; i <= r; i++)
{
// Add the highest power of
// p that divides i
cnt += countFactors(i, p);
}
return cnt;
}
// Driver code
public static void Main(String[] args)
{
int l = 2, r = 8, p = 2;
Console.WriteLine(getCount(l, r, p));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// Function to return the highest
// power of p that divides n
function countFactors(n, p)
{
let pwr = 0;
while (n > 0 && n % p == 0) {
n /= p;
pwr++;
}
return pwr;
}
// Function to return the count of times p
// appears in the prime factors of the
// elements from the range [l, r]
function getCount(l, r, p)
{
// To store the required count
let cnt = 0;
// For every element of the range
for (let i = l; i <= r; i++) {
// Add the highest power of
// p that divides i
cnt += countFactors(i, p);
}
return cnt;
}
// Driver code
let l = 2, r = 8, p = 2;
document.write(getCount(l, r, p));
</script>
Producción:
7
Espacio Auxiliar: O(1)
Enfoque eficiente: cuente los valores que son divisibles por P, P 2 , P 3 , …, P x en el rango [L, R] donde x es la mayor potencia de P tal que P x se encuentra dentro del límite superior ( P x ≤ N ). Cada iteración cuesta O(1) tiempo, por lo que la complejidad del tiempo se convierte en O(x) donde x = (log(R) / log(P)) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
// Function to return the count of times p
// appears in the prime factors of the
// elements from the range [l, r]
int getCount(int l, int r, int p)
{
// To store the required count
int cnt = 0;
int val = p;
while (1) {
// Number of values in the range [0, r]
// that are divisible by val
int a = r / val;
// Number of values in the range [0, l - 1]
// that are divisible by val
int b = (l - 1) / val;
// Increment the power of the val
val *= p;
// (a - b) is the count of numbers in the
// range [l, r] that are divisible by val
if (a - b) {
cnt += (a - b);
}
// No values that are divisible by val
// thus exiting from the loop
else
break;
}
return cnt;
}
// Driver code
int main()
{
int l = 2, r = 8, p = 2;
cout << getCount(l, r, p);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return the count of times p
// appears in the prime factors of the
// elements from the range [l, r]
static int getCount(int l, int r, int p)
{
// To store the required count
int cnt = 0;
int val = p;
while (true)
{
// Number of values in the range [0, r]
// that are divisible by val
int a = r / val;
// Number of values in the range [0, l - 1]
// that are divisible by val
int b = (l - 1) / val;
// Increment the power of the val
val *= p;
// (a - b) is the count of numbers in the
// range [l, r] that are divisible by val
if ((a - b) > 0)
{
cnt += (a - b);
}
// No values that are divisible by val
// thus exiting from the loop
else
break;
}
return cnt;
}
// Driver code
public static void main(String[] args)
{
int l = 2, r = 8, p = 2;
System.out.println(getCount(l, r, p));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach # Function to return the count of times p # appears in the prime factors of the # elements from the range [l, r] def getCount(l, r, p): # To store the required count cnt = 0; val = p; while (True): # Number of values in the range [0, r] # that are divisible by val a = r // val; # Number of values in the range [0, l - 1] # that are divisible by val b = (l - 1) // val; # Increment the power of the val val *= p; # (a - b) is the count of numbers in the # range [l, r] that are divisible by val if (a - b): cnt += (a - b); # No values that are divisible by val # thus exiting from the loop else: break; return int(cnt); # Driver Code l = 2; r = 8; p = 2; print(getCount(l, r, p)); # This code is contributed by princiraj
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the count of times p
// appears in the prime factors of the
// elements from the range [l, r]
static int getCount(int l, int r, int p)
{
// To store the required count
int cnt = 0;
int val = p;
while (true)
{
// Number of values in the range [0, r]
// that are divisible by val
int a = r / val;
// Number of values in the range [0, l - 1]
// that are divisible by val
int b = (l - 1) / val;
// Increment the power of the val
val *= p;
// (a - b) is the count of numbers in the
// range [l, r] that are divisible by val
if ((a - b) > 0)
{
cnt += (a - b);
}
// No values that are divisible by val
// thus exiting from the loop
else
break;
}
return cnt;
}
// Driver code
public static void Main(String[] args)
{
int l = 2, r = 8, p = 2;
Console.WriteLine(getCount(l, r, p));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach
// Function to return the count of times p
// appears in the prime factors of the
// elements from the range [l, r]
function getCount(l, r, p)
{
// To store the required count
let cnt = 0;
let val = p;
while (1) {
// Number of values in the range [0, r]
// that are divisible by val
let a = parseInt(r / val);
// Number of values in the range [0, l - 1]
// that are divisible by val
let b = parseInt((l - 1) / val);
// Increment the power of the val
val *= p;
// (a - b) is the count of numbers in the
// range [l, r] that are divisible by val
if (a - b) {
cnt += (a - b);
}
// No values that are divisible by val
// thus exiting from the loop
else
break;
}
return cnt;
}
// Driver code
let l = 2, r = 8, p = 2;
document.write(getCount(l, r, p));
</script>
Producción:
7
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por cr7_bullet y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA