El número primo más pequeño que falta en una array

Dada una array que contiene n números distintos. La tarea es encontrar el primo más pequeño que no está presente en la array. 
Nota: Si no falta ningún número primo hasta el elemento máximo de la array, imprima «No falta ningún número primo».
Ejemplos: 
 

Input: arr[] = {9, 11, 4, 2, 3, 7, 0, 1}
Output: 5
5 is the smallest prime, which is not present in array.

Input: arr[] = {3, 0, 2, 5}
Output: No prime number missing
As 5 is the maximum element and all prime numbers upto 5 
are present in the array.

Enfoque: en primer lugar, encuentre todos los números primos usando la criba de Eratóstenes y luego verifique secuencialmente cuál no está presente allí. Simplemente itere sobre la array y verifique si el número está allí o no usando hash .
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
// this store all prime number
// upto 10^5
// this function find all prime
vector<ll> findPrime(int MAX)
{
    bool pm[MAX + 1];
    memset(pm, true, sizeof(pm));
 
    // use sieve to find prime
    pm[0] = pm[1] = false;
    for (int i = 2; i <= MAX; i++)
        if (pm[i])
            for (int j = 2 * i; j <= MAX; j += i)
                pm[j] = false;
 
    // if number is prime then
    // store it in prime vector
    vector<ll> prime;
    for (int i = 0; i <= MAX; i++)
        if (pm[i])
            prime.push_back(i);
 
    return prime;
}
 
// Function to find the smallest prime missing
int findSmallest(int arr[], int n)
{
    int MAX = *max_element(arr, arr + n);
 
    // first of all find all prime
    vector<ll> prime = findPrime(MAX);
 
    // now store all number as index of freq arr
    // so that we can improve searching
    unordered_set<int> s;
    for (int i = 0; i < n; i++)
        s.insert(arr[i]);
 
    // now check for each prime
    int ans = -1;
    for (int i = 0; i < prime.size(); i++)
        if (s.find(prime[i]) == s.end()) {
            ans = prime[i];
            break;
        }
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 3, 0, 1, 2, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // find smallest prime
    // which is not present
    if (findSmallest(arr, n) == -1)
        cout << "No prime number missing";
    else
        cout << findSmallest(arr, n);
 
    return 0;
}

Java

// Java implementation of the above approach
import java.util.*;
 
class GFG {
 
    // this store all prime number
    // upto 10^5
    // this function find all prime
    static Vector<Integer> findPrime(int MAX)
    {
        boolean pm[] = new boolean[MAX + 1];
        for (int i = 0; i < pm.length; i++)
            pm[i] = true;
 
        // use sieve to find prime
        pm[0] = pm[1] = false;
        for (int i = 2; i <= MAX; i++)
            if (pm[i])
                for (int j = 2 * i; j <= MAX; j += i)
                    pm[j] = false;
 
        // if number is prime then
        // store it in prime vector
        Vector<Integer> prime = new Vector<Integer>();
        for (int i = 0; i <= MAX; i++)
            if (pm[i])
                prime.add(i);
 
        return prime;
    }
 
    static int max_element(int arr[])
    {
        int max = arr[0];
 
        for (int i = 0; i < arr.length; i++)
            max = Math.max(max, arr[i]);
 
        return max;
    }
 
    // Function to find the smallest prime missing
    static int findSmallest(int arr[], int n)
    {
        int MAX = max_element(arr);
 
        // first of all find all prime
        Vector<Integer> prime = findPrime(MAX);
 
        // now store all number as index of freq arr
        // so that we can improve searching
        Set<Integer> s = new HashSet<Integer>();
        for (int i = 0; i < arr.length; i++)
            s.add(arr[i]);
 
        // now check for each prime
        long ans = -1;
        for (int i = 0; i < prime.size(); i++) {
            if (!s.contains(prime.get(i))) {
 
                ans = (prime.get(i));
                break;
            }
        }
        return (int)ans;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int arr[] = { 3, 0, 1, 2, 7 };
        int n = arr.length;
 
        // find smallest prime
        // which is not present
        if (findSmallest(arr, n) == -1)
            System.out.print("No prime number missing");
        else
            System.out.print(findSmallest(arr, n));
    }
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 implementation of the above approach
 
# This function finds all
# prime numbers upto 10 ^ 5
def findPrime(MAX):
 
    pm = [True] * (MAX + 1)
 
    # use sieve to find prime
    pm[0], pm[1] = False, False
     
    for i in range(2, MAX + 1):
        if pm[i] == True:
             
            for j in range(2 * i, MAX + 1, i):
                pm[j] = False
 
    # If number is prime, then
    # store it in prime list
    prime = []
    for i in range(0, MAX + 1):
        if pm[i] == True:
            prime.append(i)
 
    return prime
 
# Function to find the smallest prime missing
def findSmallest(arr, n):
 
    MAX = max(arr)
     
    # first of all find all prime
    prime = findPrime(MAX)
 
    # now store all number as index of freq
    # arr so that we can improve searching
    s = set()
    for i in range(0, n):
        s.add(arr[i])
 
    # now check for each prime
    ans = -1
    for i in range(0, len(prime)):
        if prime[i] not in s:
            ans = prime[i]
            break
         
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    arr = [3, 0, 1, 2,  7]
    n = len(arr)
 
    # find smallest prime
    # which is not present
    if(findSmallest(arr, n) == -1):
        print("No prime number missing")
    else:
        print(findSmallest(arr, n))
 
# This code is contributed by Rituraj Jain

C#

// C# implementation of the above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
    // this store all prime number
    // upto 10^5
    // this function find all prime
    static ArrayList findPrime(int MAX)
    {
        bool[] pm = new bool[MAX + 1];
        for (int i = 0; i < MAX + 1; i++)
            pm[i] = true;
 
        // use sieve to find prime
        pm[0] = pm[1] = false;
        for (int i = 2; i <= MAX; i++)
            if (pm[i])
                for (int j = 2 * i; j <= MAX; j += i)
                    pm[j] = false;
 
        // if number is prime then
        // store it in prime vector
        ArrayList prime = new ArrayList();
        for (int i = 0; i <= MAX; i++)
            if (pm[i])
                prime.Add(i);
 
        return prime;
    }
 
    static int max_element(int []arr)
    {
        int max = arr[0];
 
        for (int i = 0; i < arr.Length; i++)
            max = Math.Max(max, arr[i]);
 
        return max;
    }
 
    // Function to find the smallest prime missing
    static int findSmallest(int []arr, int n)
    {
        int MAX = max_element(arr);
 
        // first of all find all prime
        ArrayList prime = findPrime(MAX);
 
        // now store all number as index of freq arr
        // so that we can improve searching
        HashSet<int> s = new HashSet<int>();
        for (int i = 0; i < arr.Length; i++)
            s.Add(arr[i]);
 
        // now check for each prime
        int ans = -1;
        for (int i = 0; i < prime.Count; i++)
        {
            if (!s.Contains((int)prime[i]))
            {
 
                ans = (int)(prime[i]);
                break;
            }
        }
        return (int)ans;
    }
 
    // Driver code
    static void Main()
    {
        int []arr = { 3, 0, 1, 2, 7 };
        int n = arr.Length;
 
        // find smallest prime
        // which is not present
        if (findSmallest(arr, n) == -1)
            Console.Write("No prime number missing");
        else
            Console.Write(findSmallest(arr, n));
    }
}
 
// This code is contributed by mits

Javascript

<script>
// Javascript implementation of the above approach
 
// this store all prime number
// upto 10^5
// this function find all prime
function findPrime(MAX)
{
    let pm = new Array(MAX + 1);
    pm.fill(true);
 
    // use sieve to find prime
    pm[0] = pm[1] = false;
    for (let i = 2; i <= MAX; i++)
        if (pm[i])
            for (let j = 2 * i; j <= MAX; j += i)
                pm[j] = false;
 
    // if number is prime then
    // store it in prime vector
    let prime = new Array();
    for (let i = 0; i <= MAX; i++)
        if (pm[i])
            prime.push(i);
 
    return prime;
}
 
// Function to find the smallest prime missing
function findSmallest(arr, n) {
    let MAX = arr.sort((A, B) => A - B).reverse()[0];
 
    // first of all find all prime
    let prime = findPrime(MAX);
 
    // now store all number as index of freq arr
    // so that we can improve searching
    let s = new Set();
    for (let i = 0; i < n; i++)
        s.add(arr[i]);
 
    // now check for each prime
    let ans = -1;
    for (let i = 0; i < prime.length; i++){
        if (!s.has(prime[i])) {
            ans = prime[i];
            break;
        }
    }
    return ans;
}
 
// Driver code
let arr = [3, 0, 1, 2, 7];
let n = arr.length;
 
// find smallest prime
// which is not present
if (findSmallest(arr, n) == -1)
    document.write("No prime number missing");
else
    document.write(findSmallest(arr, n));
 
// This code is contributed by gfgking.
</script>
Producción: 

5

 

Complejidad del Tiempo: O(n + MAX 2 )

Espacio Auxiliar: O(n + MAX)

Publicación traducida automáticamente

Artículo escrito por sahilshelangia 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 *