Dada una array arr[] de N enteros positivos y un entero K ., la tarea es crear un conjunto de números primos tal que la suma de todas las potencias de los números primos en la descomposición en factores primos de todos los elementos de la array sea divisible por K .
Ejemplos:
Entrada: arr[] = {1, 2, 3}, K = 1
Salida: {2, 3}
Explicación:
2 = 2 1
3 = 3 1
La potencia de 2 es 1, que es divisible por K(=1).
La potencia de 2 es 1, que es divisible por K(=1).Entrada: arr[] = {2, 2, 4, 8}, K = 10
Salida: {}
Explicación:
2 = 2 1
2 = 2 1
4 = 2 2
8 = 2 3
La potencia de 2 es (1 + 1 + 2 + 3) = 7 que no es divisible por K(=10).
Por lo tanto, el conjunto vacío de salida.
Enfoque ingenuo: la idea es encontrar todos los números primos menores o iguales que el elemento máximo de la array arr[] . Para cada número primo, cuente el número de veces, divide el elemento de la array. Si el valor de count es divisible por K , inserte el número primo en el conjunto resultante. Al final imprimir elementos del conjunto.
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es calcular previamente el recuento de todos los factores primos de todos los números. A continuación se muestran los pasos:
- Cree la array de factorización prima más pequeña spf[] hasta el número máximo en la array. Este paso se utiliza para precalcular los factores primos de un número .
- Recorra la array dada arr[] y para cada elemento encuentre la suma de todos los factores almacenados en la array spf[] .
- Para cada suma de la potencia de un número primo en los pasos anteriores, almacena su frecuencia en un mapa .
- Recorra el mapa si, para cualquier número, la frecuencia es divisible por K y luego almacene ese número.
- Finalmente, imprima todos los números almacenados en el paso anterior.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
// To store the smallest prime
// factor till 10^5
int spf[10001];
// Function to compute smallest
// prime factor array
void spf_array(int spf[])
{
// Initialize the spf array
// first element
spf[1] = 1;
for (int i = 2; i < 1000; i++)
// Marking smallest prime
// factor for every number
// to be itself
spf[i] = i;
// Separately marking smallest
// prime factor for every even
// number as 2
for (int i = 4; i < 1000; i += 2)
spf[i] = 2;
for (int i = 3; i * i < 1000; i++) {
// Checking if i is prime
if (spf[i] == i) {
// Marking SPF for all
// numbers divisible by i
for (int j = i * i;
j < 1000; j += i)
// Marking spf[j] if it is
// not previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function that finds minimum operation
void frequent_prime(int arr[], int N,
int K)
{
// Create a spf[] array
spf_array(spf);
// Map created to store the
// unique prime numbers
unordered_map<int, int> Hmap;
// To store the result
vector<int> result;
int i = 0;
// To store minimum operations
int c = 0;
// To store every unique
// prime number
for (i = 0; i < N; i++) {
int x = arr[i];
while (x != 1) {
Hmap[spf[x]]
= Hmap[spf[x]] + 1;
x = x / spf[x];
}
}
// Erase 1 as a key because
// it is not a prime number
Hmap.erase(1);
for (auto x : Hmap) {
// First Prime Number
int primeNum = x.first;
int frequency = x.second;
// Frequency is divisible
// by K then insert primeNum
// in the result[]
if (frequency % K == 0) {
result.push_back(primeNum);
}
}
// Print the elements
// if it exists
if (result.size() > 0) {
for (auto& it : result) {
cout << it << ' ';
}
}
else {
cout << "{}";
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 4, 6 };
// Given K
int K = 1;
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
frequent_prime(arr, N, K);
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// To store the smallest prime
// factor till 10^5
static int[] spf = new int[10001];
// Function to compute smallest
// prime factor array
static void spf_array(int spf[])
{
// Initialize the spf array
// first element
spf[1] = 1;
for(int i = 2; i < 1000; i++)
// Marking smallest prime
// factor for every number
// to be itself
spf[i] = i;
// Separately marking smallest
// prime factor for every even
// number as 2
for(int i = 4; i < 1000; i += 2)
spf[i] = 2;
for(int i = 3; i * i < 1000; i++)
{
// Checking if i is prime
if (spf[i] == i)
{
// Marking SPF for all
// numbers divisible by i
for(int j = i * i;
j < 1000; j += i)
// Marking spf[j] if it is
// not previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function that finds minimum operation
static void frequent_prime(int arr[], int N,
int K)
{
// Create a spf[] array
spf_array(spf);
// Map created to store the
// unique prime numbers
Map<Integer, Integer> Hmap = new TreeMap<>();
// To store the result
ArrayList<Integer> result = new ArrayList<>();
int i = 0;
// To store minimum operations
int c = 0;
// To store every unique
// prime number
for(i = 0; i < N; i++)
{
int x = arr[i];
while (x != 1)
{
Hmap.put(spf[x],
Hmap.getOrDefault(spf[x], 0) + 1);
x = x / spf[x];
}
}
// Erase 1 as a key because
// it is not a prime number
Hmap.remove(1);
for(Map.Entry<Integer,
Integer> x : Hmap.entrySet())
{
// First prime number
int primeNum = x.getKey();
int frequency = x.getValue();
// Frequency is divisible
// by K then insert primeNum
// in the result[]
if (frequency % K == 0)
{
result.add(primeNum);
}
}
// Print the elements
// if it exists
if (result.size() > 0)
{
for(Integer it : result)
{
System.out.print(it + " ");
}
}
else
{
System.out.print("{}");
}
}
// Driver code
public static void main (String[] args)
{
// Given array arr[]
int arr[] = { 1, 4, 6 };
// Given K
int K = 1;
int N = arr.length;
// Function call
frequent_prime(arr, N, K);
}
}
// This code is contributed by offbeat
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// To store the smallest prime
// factor till 10^5
static int[] spf = new int[10001];
// Function to compute smallest
// prime factor array
static void spf_array(int[] spf)
{
// Initialize the spf array
// first element
spf[1] = 1;
for (int i = 2; i < 1000; i++)
// Marking smallest prime
// factor for every number
// to be itself
spf[i] = i;
// Separately marking smallest
// prime factor for every even
// number as 2
for (int i = 4; i < 1000; i += 2)
spf[i] = 2;
for (int i = 3; i * i < 1000; i++)
{
// Checking if i is prime
if (spf[i] == i)
{
// Marking SPF for all
// numbers divisible by i
for (int j = i * i; j < 1000; j += i)
// Marking spf[j] if it is
// not previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function that finds minimum operation
static void frequent_prime(int[] arr, int N, int K)
{
// Create a spf[] array
spf_array(spf);
// Map created to store the
// unique prime numbers
SortedDictionary<int,
int> Hmap = new SortedDictionary<int,
int>();
// To store the result
List<int> result = new List<int>();
int i = 0;
// To store every unique
// prime number
for (i = 0; i < N; i++)
{
int x = arr[i];
while (x != 1)
{
if (Hmap.ContainsKey(spf[x]))
Hmap[spf[x]] = spf[x] + 1;
else
Hmap.Add(spf[x], 1);
x = x / spf[x];
}
}
// Erase 1 as a key because
// it is not a prime number
Hmap.Remove(1);
foreach(KeyValuePair<int, int> x in Hmap)
{
// First prime number
int primeNum = x.Key;
int frequency = x.Value;
// Frequency is divisible
// by K then insert primeNum
// in the result[]
if (frequency % K == 0)
{
result.Add(primeNum);
}
}
// Print the elements
// if it exists
if (result.Count > 0)
{
foreach(int it in result)
{
Console.Write(it + " ");
}
}
else
{
Console.Write("{}");
}
}
// Driver code
public static void Main(String[] args)
{
// Given array []arr
int[] arr = {1, 4, 6};
// Given K
int K = 1;
int N = arr.Length;
// Function call
frequent_prime(arr, N, K);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for the above approach
# To store the smallest prime
# factor till 10^5
spf = [0 for i in range(10001)]
# Function to compute smallest
# prime factor array
def spf_array(spf):
# Initialize the spf array
# first element
spf[1] = 1
for i in range(2, 1000, 1):
# Marking smallest prime
# factor for every number
# to be itself
spf[i] = i
# Separately marking smallest
# prime factor for every even
# number as 2
for i in range(4, 1000, 2):
spf[i] = 2
i = 3
while( i* i < 1000):
# Checking if i is prime
if (spf[i] == i):
# Marking SPF for all
# numbers divisible by i
j = i * i
while(j < 1000):
# Marking spf[j] if it is
# not previously marked
if (spf[j] == j):
spf[j] = i
j += i
i += 1
# Function that finds minimum operation
def frequent_prime(arr, N, K):
# Create a spf[] array
spf_array(spf)
# Map created to store the
# unique prime numbers
Hmap = {}
# To store the result
result = []
i = 0
# To store minimum operations
c = 0
# To store every unique
# prime number
for i in range(N):
x = arr[i]
while (x != 1):
Hmap[spf[x]] = Hmap.get(spf[x], 0) + 1
x = x // spf[x]
# Erase 1 as a key because
# it is not a prime number
if (1 in Hmap):
Hmap.pop(1)
for key, value in Hmap.items():
# First Prime Number
primeNum = key
frequency = value
# Frequency is divisible
# by K then insert primeNum
# in the result[]
if (frequency % K == 0):
result.append(primeNum)
# Print the elements
# if it exists
result = result[::-1]
if (len(result) > 0):
for it in result:
print(it, end = " ")
else:
print("{}")
# Driver Code
if __name__ == '__main__':
# Given array arr[]
arr = [ 1, 4, 6 ]
# Given K
K = 1
N = len(arr)
# Function Call
frequent_prime(arr, N, K)
# This code is contributed by ipg2016107
Javascript
<script>
// JavaScript program for the above approach
// To store the smallest prime
// factor till 10^5
var spf = Array(10001);
// Function to compute smallest
// prime factor array
function spf_array(spf)
{
// Initialize the spf array
// first element
spf[1] = 1;
for (var i = 2; i < 1000; i++)
// Marking smallest prime
// factor for every number
// to be itself
spf[i] = i;
// Separately marking smallest
// prime factor for every even
// number as 2
for (var i = 4; i < 1000; i += 2)
spf[i] = 2;
for (var i = 3; i * i < 1000; i++) {
// Checking if i is prime
if (spf[i] == i) {
// Marking SPF for all
// numbers divisible by i
for (var j = i * i;
j < 1000; j += i)
// Marking spf[j] if it is
// not previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function that finds minimum operation
function frequent_prime(arr, N, K)
{
// Create a spf[] array
spf_array(spf);
// Map created to store the
// unique prime numbers
var Hmap = new Map();
// To store the result
var result = [];
var i = 0;
// To store minimum operations
var c = 0;
// To store every unique
// prime number
for (i = 0; i < N; i++) {
var x = arr[i];
while (x != 1) {
if(Hmap.has(spf[x]))
Hmap.set(spf[x], Hmap.get(spf[x])+1)
else
Hmap.set(spf[x], 1);
x = parseInt(x / spf[x]);
}
}
// Erase 1 as a key because
// it is not a prime number
Hmap.delete(1);
Hmap.forEach((value, key) => {
// First Prime Number
var primeNum = key;
var frequency = value;
// Frequency is divisible
// by K then insert primeNum
// in the result[]
if (frequency % K == 0) {
result.push(primeNum);
}
});
// Print the elements
// if it exists
if (result.length > 0) {
result.forEach(it => {
document.write(it+" ");
});
}
else {
document.write( "{}");
}
}
// Driver Code
// Given array arr[]
var arr = [1, 4, 6];
// Given K
var K = 1;
var N = arr.length;
// Function Call
frequent_prime(arr, N, K);
</script>
Producción:
3 2
Complejidad temporal: O(M*log(M)), donde M es el elemento máximo del arreglo. Espacio
Auxiliar : O(M)
Publicación traducida automáticamente
Artículo escrito por vabzcode12 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA