Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar el número de elementos de la array cuya cuenta de divisores es un número primo .
Ejemplos:
Entrada: arr[] = {3, 6, 4}
Salida: 2
Explicación:
El recuento de divisores para cada elemento es:
- arr[0]( = 3): 3 tiene 2 divisores, es decir, 1 y 3.
- arr[1]( = 6): 6 tiene 4 divisores, es decir, 1, 2, 3 y 6.
- arr[2]( = 4): 4 tiene 3 divisores, es decir, 1, 2 y 4.
Por lo tanto, solo hay 2 elementos de array, es decir, {3, 4}, cuya cuenta de divisores es un número primo.
Entrada: arr[] = {10, 13, 17, 25}
Salida: 3
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es encontrar el número de divisores para cada elemento de la array y verificar si el conteo de divisores es un número primo o no. Si se encuentra que es cierto, entonces incremente el conteo . De lo contrario, busque el siguiente elemento. Después de verificar todos los elementos de la array, imprima el conteo obtenido.
Complejidad de Tiempo: O(N (3/2) )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar precomputando los números primos usando la criba de Eratóstenes . Siga los pasos a continuación para resolver el problema dado:
- Inicialice una variable, digamos count , para almacenar el recuento de elementos de array cuyo recuento de divisores es un número primo .
- Almacene todos los números primos hasta el elemento máximo de la array en una array booleana, digamos prime[] , usando Sieve of Eratosthenes .
- Ahora encuentre el conteo de divisores de elementos hasta el elemento máximo de la array y guárdelos en una array, digamos countDivisor[] .
- Recorra la array dada arr[] y para cada elemento arr[i] y si el valor de countDivisor[arr[i]] es primo, entonces incremente el conteo en 1 . De lo contrario, busque el siguiente elemento.
- Después de completar los pasos anteriores, imprima el valor de conteo como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the array elements
// whose count of divisors is prime
int primeDivisors(int arr[], int N)
{
// Stores the maximum element
int K = arr[0];
// Find the maximum element
for (int i = 1; i < N; i++) {
K = max(K, arr[i]);
}
// Store if i-th element is
// prime(0) or non-prime(1)
int prime[K + 1] = { 0 };
// Base Case
prime[0] = 1;
prime[1] = 1;
for (int i = 2; i < K + 1; i++) {
// If i is a prime number
if (!prime[i]) {
// Mark all multiples
// of i as non-prime
for (int j = 2 * i;
j < K + 1; j += i) {
prime[j] = 1;
}
}
}
// Stores the count of divisors
int factor[K + 1] = { 0 };
// Base Case
factor[0] = 0;
factor[1] = 1;
for (int i = 2; i < K + 1; i++) {
factor[i] += 1;
// Iterate to count factors
for (int j = i; j < K + 1;
j += i) {
factor[j] += 1;
}
}
// Stores the count of array
// elements whose count of
// divisors is a prime number
int count = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// If count of divisors is prime
if (prime[factor[arr[i]]] == 0)
count++;
}
// Return the resultant count
return count;
}
// Driver Code
int main()
{
int arr[] = { 10, 13, 17, 25 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << primeDivisors(arr, N);
return 0;
}
Java
// Java program for the above approach
public class GFG
{
// Function to count the array elements
// whose count of divisors is prime
public static int primeDivisors(int[] arr, int N)
{
// Stores the maximum element
int K = arr[0];
// Find the maximum element
for (int i = 1; i < N; i++) {
K = Math.max(K, arr[i]);
}
// Store if i-th element is
// prime(0) or non-prime(1)
int[] prime = new int[K + 1];
// Base Case
prime[0] = 1;
prime[1] = 1;
for (int i = 2; i < K + 1; i++) {
// If i is a prime number
if (prime[i] == 0) {
// Mark all multiples
// of i as non-prime
for (int j = 2 * i; j < K + 1; j += i) {
prime[j] = 1;
}
}
}
// Stores the count of divisors
int[] factor = new int[K + 1];
// Base Case
factor[0] = 0;
factor[1] = 1;
for (int i = 2; i < K + 1; i++) {
factor[i] += 1;
// Iterate to count factors
for (int j = i; j < K + 1; j += i) {
factor[j] += 1;
}
}
// Stores the count of array
// elements whose count of
// divisors is a prime number
int count = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// If count of divisors is prime
if (prime[factor[arr[i]]] == 0)
count++;
}
// Return the resultant count
return count;
}
// Driver Code
public static void main(String args[]) {
int[] arr = { 10, 13, 17, 25 };
int N = arr.length;
System.out.println(primeDivisors(arr, N));
}
}
// This code is contributed by SoumikMondal.
Python3
# Python3 program for the above approach # Function to count the array elements # whose count of divisors is prime def primeDivisors(arr, N): # Stores the maximum element K = arr[0] # Find the maximum element for i in range(1, N): K = max(K, arr[i]) # Store if i-th element is # prime(0) or non-prime(1) prime = [0] * (K + 1) # Base Case prime[0] = 1 prime[1] = 1 for i in range(2, K + 1): # If i is a prime number if (not prime[i]): # Mark all multiples # of i as non-prime for j in range(2 * i, K + 1, i): prime[j] = 1 # Stores the count of divisors factor = [0] * (K + 1) # Base Case factor[0] = 0 factor[1] = 1 for i in range(2, K + 1): factor[i] += 1 # Iterate to count factors for j in range(i, K + 1, i): factor[j] += 1 # Stores the count of array # elements whose count of # divisors is a prime number count = 0 # Traverse the array arr[] for i in range(N): # If count of divisors is prime if (prime[factor[arr[i]]] == 0): count += 1 # Return the resultant count return count # Driver Code if __name__ == '__main__': arr = [ 10, 13, 17, 25 ] N = len(arr) print (primeDivisors(arr, N)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG
{
// Function to count the array elements
// whose count of divisors is prime
static int primeDivisors(int[] arr, int N)
{
// Stores the maximum element
int K = arr[0];
// Find the maximum element
for (int i = 1; i < N; i++) {
K = Math.Max(K, arr[i]);
}
// Store if i-th element is
// prime(0) or non-prime(1)
int[] prime = new int[K + 1];
// Base Case
prime[0] = 1;
prime[1] = 1;
for (int i = 2; i < K + 1; i++) {
// If i is a prime number
if (prime[i] == 0) {
// Mark all multiples
// of i as non-prime
for (int j = 2 * i; j < K + 1; j += i) {
prime[j] = 1;
}
}
}
// Stores the count of divisors
int[] factor = new int[K + 1];
// Base Case
factor[0] = 0;
factor[1] = 1;
for (int i = 2; i < K + 1; i++) {
factor[i] += 1;
// Iterate to count factors
for (int j = i; j < K + 1; j += i) {
factor[j] += 1;
}
}
// Stores the count of array
// elements whose count of
// divisors is a prime number
int count = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// If count of divisors is prime
if (prime[factor[arr[i]]] == 0)
count++;
}
// Return the resultant count
return count;
}
// Driver Code
public static void Main()
{
int[] arr = { 10, 13, 17, 25 };
int N = arr.Length;
Console.WriteLine(primeDivisors(arr, N));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript program for the above approach
// Function to count the array elements
// whose count of divisors is prime
function primeDivisors(arr, N)
{
// Stores the maximum element
var K = arr[0];
var i,j;
// Find the maximum element
for (i = 1; i < N; i++) {
K = Math.max(K, arr[i]);
}
// Store if i-th element is
// prime(0) or non-prime(1)
var prime = Array(K + 1).fill(0);
// Base Case
prime[0] = 1;
prime[1] = 1;
for (i = 2; i < K + 1; i++) {
// If i is a prime number
if (prime[i]==0) {
// Mark all multiples
// of i as non-prime
for (j = 2 * i;
j < K + 1; j += i) {
prime[j] = 1;
}
}
}
// Stores the count of divisors
var factor = Array(K + 1).fill(0);
// Base Case
factor[0] = 0;
factor[1] = 1;
for (i = 2; i < K + 1; i++) {
factor[i] += 1;
// Iterate to count factors
for (j = i; j < K + 1;
j += i) {
factor[j] += 1;
}
}
// Stores the count of array
// elements whose count of
// divisors is a prime number
var count = 0;
// Traverse the array arr[]
for (i = 0; i < N; i++) {
// If count of divisors is prime
if (prime[factor[arr[i]]] == 0)
count++;
}
// Return the resultant count
return count;
}
// Driver Code
var arr = [10, 13, 17, 25];
var N = arr.length;
document.write(primeDivisors(arr, N));
</script>
Producción:
3
Complejidad de tiempo: O(M*log M), donde M es el elemento máximo de la array dada .
Espacio Auxiliar: O(M)
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA