Dada una array arr[] de N enteros positivos. La tarea es encontrar los elementos primos mínimo y máximo en la array dada.
Ejemplos:
Input: arr[] = 1, 3, 4, 5, 7
Output: Minimum : 3
Maximum : 7
Input: arr[] = 1, 2, 3, 4, 5, 6, 7, 11
Output: Minimum : 2
Maximum : 11
Enfoque ingenuo:
tome una variable min y max. Inicialice min con INT_MAX y max con INT_MIN. Recorra la array y siga verificando cada elemento si es primo o no y actualice el elemento primo mínimo y máximo al mismo tiempo.
Enfoque eficiente:
genere todos los números primos hasta el elemento máximo de la array utilizando el tamiz de Eratóstenes y guárdelos en un hash. Ahora recorra la array y encuentre el elemento mínimo y máximo que son primos usando la tabla hash.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find minimum and maximum
// prime number in given array.
#include <bits/stdc++.h>
using namespace std;
// Function to find count of prime
void prime(int arr[], int n)
{
// Find maximum value in the array
int max_val = *max_element(arr, arr + n);
// USE SIEVE TO FIND ALL PRIME NUMBERS LESS
// THAN OR EQUAL TO max_val
// Create a boolean array "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
vector<bool> prime(max_val + 1, true);
// Remaining part of SIEVE
prime[0] = false;
prime[1] = false;
for (int p = 2; p * p <= max_val; 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 <= max_val; i += p)
prime[i] = false;
}
}
// Minimum and Maximum prime number
int minimum = INT_MAX;
int maximum = INT_MIN;
for (int i = 0; i < n; i++)
if (prime[arr[i]]) {
minimum = min(minimum, arr[i]);
maximum = max(maximum, arr[i]);
}
cout << "Minimum : " << minimum << endl;
cout << "Maximum : " << maximum << endl;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
prime(arr, n);
return 0;
}
Java
// Java program to find minimum and maximum
// prime number in given array.
import java.util.*;
class GFG {
// Function to find count of prime
static void prime(int arr[], int n)
{
// Find maximum value in the array
int max_val = Arrays.stream(arr).max().getAsInt();
// USE SIEVE TO FIND ALL PRIME NUMBERS LESS
// THAN OR EQUAL TO max_val
// Create a boolean array "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
Vector<Boolean> prime = new Vector<Boolean>();
for(int i= 0;i<max_val+1;i++)
prime.add(Boolean.TRUE);
// Remaining part of SIEVE
prime.add(0, Boolean.FALSE);
prime.add(1, Boolean.FALSE);
for (int p = 2; p * p <= max_val; p++) {
// If prime[p] is not changed, then
// it is a prime
if (prime.get(p) == true) {
// Update all multiples of p
for (int i = p * 2; i <= max_val; i += p)
prime.add(i, Boolean.FALSE);
}
}
// Minimum and Maximum prime number
int minimum = Integer.MAX_VALUE;
int maximum = Integer.MIN_VALUE;
for (int i = 0; i < n; i++)
if (prime.get(arr[i])) {
minimum = Math.min(minimum, arr[i]);
maximum = Math.max(maximum, arr[i]);
}
System.out.println("Minimum : " + minimum) ;
System.out.println("Maximum : " + maximum );
}
// Driver code
public static void main(String[] args) {
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int n = arr.length;
prime(arr, n);
}
}
/*This code is contributed by 29AjayKumar*/
Python3
# Python3 program to find minimum and
# maximum prime number in given array.
import math as mt
# Function to find count of prime
def Prime(arr, n):
# Find maximum value in the array
max_val = max(arr)
# USE SIEVE TO FIND ALL PRIME NUMBERS
# LESS THAN OR EQUAL TO max_val
# Create a boolean array "prime[0..n]".
# A value in prime[i] will finally be
# false if i is Not a prime, else true.
prime = [True for i in range(max_val + 1)]
# Remaining part of SIEVE
prime[0] = False
prime[1] = False
for p in range(2, mt.ceil(mt.sqrt(max_val))):
# If prime[p] is not changed,
# then it is a prime
if (prime[p] == True):
# Update all multiples of p
for i in range(2 * p, max_val + 1, p):
prime[i] = False
# Minimum and Maximum prime number
minimum = 10**9
maximum = -10**9
for i in range(n):
if (prime[arr[i]] == True):
minimum = min(minimum, arr[i])
maximum = max(maximum, arr[i])
print("Minimum : ", minimum )
print("Maximum : ", maximum )
# Driver code
arr = [1, 2, 3, 4, 5, 6, 7]
n = len(arr)
Prime(arr, n)
# This code is contributed by
# Mohit kumar 29
C#
// A C# program to find minimum and maximum
// prime number in given array.
using System;
using System.Linq;
using System.Collections.Generic;
class GFG
{
// Function to find count of prime
static void prime(int []arr, int n)
{
// Find maximum value in the array
int max_val = arr.Max();
// USE SIEVE TO FIND ALL PRIME NUMBERS LESS
// THAN OR EQUAL TO max_val
// Create a boolean array "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
List<bool>prime = new List<bool>();
for(int i = 0; i < max_val + 1;i++)
prime.Add(true);
// Remaining part of SIEVE
prime.Insert(0, false);
prime.Insert(1, false);
for (int p = 2; p * p <= max_val; 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 <= max_val; i += p)
prime.Insert(i, false);
}
}
// Minimum and Maximum prime number
int minimum = int.MaxValue;
int maximum = int.MinValue;
for (int i = 0; i < n; i++)
if (prime[arr[i]])
{
minimum = Math.Min(minimum, arr[i]);
maximum = Math.Max(maximum, arr[i]);
}
Console.WriteLine("Minimum : " + minimum) ;
Console.WriteLine("Maximum : " + maximum );
}
// Driver code
public static void Main()
{
int []arr = { 1, 2, 3, 4, 5, 6, 7 };
int n = arr.Length;
prime(arr, n);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript program to find minimum and maximum
// prime number in given array.
// Function to find count of prime
function prime(arr, n)
{
// Find maximum value in the array
let max_val = arr.sort((b, a) => a - b)[0];
// USE SIEVE TO FIND ALL PRIME NUMBERS LESS
// THAN OR EQUAL TO max_val
// Create a boolean array "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
let prime = new Array(max_val + 1).fill(true);
// Remaining part of SIEVE
prime[0] = false;
prime[1] = false;
for (let p = 2; p * p <= max_val; p++) {
// If prime[p] is not changed, then
// it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (let i = p * 2; i <= max_val; i += p)
prime[i] = false;
}
}
// Minimum and Maximum prime number
let minimum = Number.MAX_SAFE_INTEGER;
let maximum = Number.MIN_SAFE_INTEGER;
for (let i = 0; i < n; i++)
if (prime[arr[i]]) {
minimum = Math.min(minimum, arr[i]);
maximum = Math.max(maximum, arr[i]);
}
document.write("Minimum : " + minimum + "<br>");
document.write("Maximum : " + maximum + "<br>");
}
// Driver code
let arr = [1, 2, 3, 4, 5, 6, 7];
let n = arr.length;
prime(arr, n);
// This code is contributed by Saurabh Jaiswal
</script>
Producción:
Minimum : 2 Maximum : 7
Complejidad del tiempo: O(n*log(log(n)))
Publicación traducida automáticamente
Artículo escrito por VishalBachchas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA