Dados tres enteros A, B y K. Necesitamos encontrar no. de números K-primos en el rango [A, B]. Un número se llama K-primo si tiene exactamente K factores primos distintos.
Ejemplos:
Input : A = 4, B = 10, K = 2. Output : 6 10 Given range is [4, 5, 6, 7, 8, 9, 10]. From the above range 6 and 10 have 2 distinct prime factors, 6 = 3*2; 10 = 5*2. Input : A = 14, B = 18, K = 2. Output : 14 15 18 Range = [14, 15]. Both 14, 15 and 18 have 2 distinct prime factors, 14 = 7*2, 15 = 3*5 and 18 = 2*3*3
Una solución simple es atravesar el rango dado. Para cada elemento del rango, encuentre sus factores primos . Finalmente imprime todos aquellos números cuyos factores primos sean k.
Una solución eficiente es usar el Algoritmo Tamiz de Eratóstenes
prime[n] = {true};
for (int p=2; p*p<=n; p++)
{
// If prime[p] is not changed, then
// it is a prime
if (prime[p] == true)
{
// Update all multiples of p
for (int i=p*2; i<=n; i += p)
prime[i] = false;
}
}
Si observamos claramente el algoritmo anterior, tiene la propiedad de iterar a través de todos los múltiplos de números primos menores que N. Entonces, la cantidad de veces que el algoritmo marca un número no primo es igual a la cantidad de factores primos de ese número. Para lograr esto, mantenga una array llamada marcada y aumente la cuenta de un número cada vez que el algoritmo lo marque como no primo. Y en el siguiente paso, iteramos a través de todos los números en el rango [A, B] y aumentamos nuestra cuenta de k-números primos si están marcados [número] == K.
C++
// CPP program to count all those numbers in
// given range whose count of prime factors
// is k
#include <bits/stdc++.h>
using namespace std;
void printKPFNums(int A, int B, int K)
{
// Count prime factors of all numbers
// till B.
bool prime[B+1] = { true };
int p_factors[B+1] = { 0 };
for (int p = 2; p <= B; p++)
if (p_factors[p] == 0)
for (int i = p; i <= B; i += p)
p_factors[i]++;
// Print all numbers with k prime factors
for (int i = A; i <= B; i++)
if (p_factors[i] == K)
cout << i << " ";
}
// Driver code
int main()
{
int A = 14, B = 18, K = 2;
printKPFNums(A, B, K);
return 0;
}
Java
// Java program to count
// all those numbers in
// given range whose count
// of prime factors
// is k
import java.io.*;
import java.util.*;
class GFG {
static void printKPFNums(int A, int B, int K)
{
// Count prime factors of all numbers
// till B.
int p_factors[] = new int[B+1];
Arrays.fill(p_factors,0);
for (int p = 2; p <= B; p++)
if (p_factors[p] == 0)
for (int i = p; i <= B; i += p)
p_factors[i]++;
// Print all numbers with k prime factors
for (int i = A; i <= B; i++)
if (p_factors[i] == K)
System.out.print( i + " ");
}
// Driver code
public static void main(String args[])
{
int A = 14, B = 18, K = 2;
printKPFNums(A, B, K);
}
}
// This code is contributed
// by Nikita Tiwari.
Python3
# Python 3 program to count # all those numbers in # given range whose count # of prime factors # is k def printKPFNums(A, B, K) : # Count prime factors # of all numbers # till B. prime = [ True]*(B+1) p_factors= [ 0 ]*(B+1) for p in range(2,B+1) : if (p_factors[p] == 0) : for i in range(p,B+1,p) : p_factors[i] = p_factors[i] + 1 # Print all numbers with # k prime factors for i in range(A,B+1) : if (p_factors[i] == K) : print( i ,end=" ") # Driver code A = 14 B = 18 K = 2 printKPFNums(A, B, K) # This code is contributed # by Nikita Tiwari.
C#
// C# program to count all
// those numbers in given
// range whose count of
// prime factors is k
using System;
class GFG {
static void printKPFNums(int A, int B,
int K)
{
// Count prime factors of
// all numbers till B.
bool []prime = new bool[B + 1];
for(int i = 0; i < B + 1; i++)
prime[i] = true;
int []p_factors = new int[B + 1];
for(int i = 0; i < B + 1; i++)
p_factors[i] = 0;
for (int p = 2; p <= B; p++)
if (p_factors[p] == 0)
for (int i = p; i <= B; i += p)
p_factors[i]++;
// Print all numbers with
// k prime factors
for (int i = A; i <= B; i++)
if (p_factors[i] == K)
Console.Write( i + " ");
}
// Driver code
public static void Main()
{
int A = 14, B = 18, K = 2;
printKPFNums(A, B, K);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to count all those numbers
// in given range whose count of prime
// factors is k
function printKPFNums($A, $B, $K)
{
// Count prime factors of all
// numbers till B.
$prime = array_fill(true, $B + 1, NULL);
$p_factors = array_fill(0, $B + 1, NULL);
for ($p = 2; $p <= $B; $p++)
if ($p_factors[$p] == 0)
for ($i = $p; $i <= $B; $i += $p)
$p_factors[$i]++;
// Print all numbers with
// k prime factors
for ($i = $A; $i <= $B; $i++)
if ($p_factors[$i] == $K)
echo $i . " ";
}
// Driver code
$A = 14;
$B = 18;
$K = 2;
printKPFNums($A, $B, $K);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to count all those
// numbers in given range whose count
// of prime factors is k
// Returns the sum of first
// n odd numbers
function prletKPFNums(A, B, K)
{
// Count prime factors of
// all numbers till B.
let prime = [];
for(let i = 0; i < B + 1; i++)
prime[i] = true;
let p_factors = [];
for(let i = 0; i < B + 1; i++)
p_factors[i] = 0;
for (let p = 2; p <= B; p++)
if (p_factors[p] == 0)
for(let i = p; i <= B; i += p)
p_factors[i]++;
// Print let all numbers with
// k prime factors
for(let i = A; i <= B; i++)
if (p_factors[i] == K)
document.write( i + " ");
}
// Driver code
let A = 14, B = 18, K = 2;
prletKPFNums(A, B, K);
// This code is contributed by sanjoy_62
</script>
Producción:
14 15 18
Complejidad de tiempo: O(B 2 ), B es el rango
Espacio auxiliar: O(B), B es el rango
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 Harsha_Mogali y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA