K-Primos (Números con k factores primos) en un rango

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *