Сумма и произведение k наименьших и k наибольших простых чисел в массиве

Опубликовано: 3 Декабря, 2021

Учитывая целое число k и массив целых чисел arr , задача состоит в том, чтобы найти сумму и произведение k наименьших и k наибольших простых чисел в массиве.
Предположим, что в массиве не менее k простых чисел.

Примеры:

Input: arr[] = {2, 5, 6, 8, 10, 11}, k = 2
Output: Sum of k-minimum prime numbers is 7
Sum of k-maximum prime numbers is 16
Product of k-minimum prime numbers is 10
Product of k-maximum prime numbers is 55
{2, 5, 11} are the only prime numbers from the array. {2, 5} are the 2 smallest and {5, 11} are the 2 largest among them.
Input: arr[] = {4, 2, 12, 13, 5, 19}, k = 3
Output: Sum of k-minimum prime numbers is 20
Sum of k-maximum prime numbers is 37
Product of k-minimum prime numbers is 130
Product of k-maximum prime numbers is 1235

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:

Используя Sieve of Eratosthenes, сгенерируйте логический вектор до размера максимального элемента из массива, который можно использовать, чтобы проверить, является ли число простым или нет.
Также установите 0 и 1 как непростые, чтобы они не считались простыми числами.
Теперь пройдитесь по массиву и вставьте все числа, которые являются простыми в две кучи: минимальную и максимальную.
Теперь вытащите k верхних элементов из минимальной кучи и возьмите сумму и произведение минимальных k простых чисел.
Сделайте то же самое с максимальной кучей, чтобы получить сумму и произведение максимальных k простых чисел.
Наконец, распечатайте результаты.

Ниже представлена реализация описанного выше подхода:

C ++

 // C++ program to find the sum
 // and product of k smallest and
 // k largest prime numbers in an array
 #include <bits/stdc++.h>
 using namespace std;
 
vector< bool > SieveOfEratosthenes( int max_val)
 {
    // Create a boolean vector "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 );
    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 ;
        }
    }
    return prime;
 }
 
// Function that calculates the sum
 // and product of k smallest and k
 // largest prime numbers in an array
 void primeSumAndProduct( int arr[], int n, int k)
 {
    // 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
    vector< bool > prime = SieveOfEratosthenes(max_val);
 
    // Set 0 and 1 as non-primes as
    // they don't need to be
    // counted as prime numbers
    prime[0] = false ;
    prime[1] = false ;
 
    // Max Heap to store all the prime numbers
    priority_queue< int > maxHeap;
 
    // Min Heap to store all the prime numbers
    priority_queue< int , vector< int >, greater< int >>
        minHeap;
 
    // Push all the prime numbers
    // from the array to the heaps
    for ( int i = 0; i < n; i++)
        if (prime[arr[i]]) {
            minHeap.push(arr[i]);
            maxHeap.push(arr[i]);
        }
    long long int minProduct = 1
        , maxProduct = 1
        , minSum = 0
        , maxSum = 0;
    while (k--) {
 
        // Calculate the products
        minProduct *= minHeap.top();
        maxProduct *= maxHeap.top();
 
        // Calculate the sum
        minSum += minHeap.top();
        maxSum += maxHeap.top();
 
        // Pop the current minimum element
        minHeap.pop();
 
        // Pop the current maximum element
        maxHeap.pop();
    }
 
    cout << "Sum of k-minimum prime numbers is "
         << minSum << "
" ;
    cout << "Sum of k-maximum prime numbers is "
         << maxSum << "
" ;
    cout << "Product of k-minimum prime numbers is "
         << minProduct << "
" ;
    cout << "Product of k-maximum prime numbers is "
         << maxProduct;
 }
 
// Driver code
 int main()
 {
 
    int arr[] = { 4, 2, 12, 13, 5, 19 };
    int n = sizeof (arr) / sizeof (arr[0]);
 
    int k = 3;
 
    primeSumAndProduct(arr, n, k);
 
    return 0;
 }

Джава

 // Java program to find the sum
 // and product of k smallest and
 // k largest prime numbers in an array
 import java.util.*;
 
class GFG
 {
    public static void main(String[] args)
    {
        int arr[] = { 4 , 2 , 12 , 13 , 5 , 19 };
        int n = arr.length;
        int k = 3 ;
        primeSumAndProduct(arr, n, k);
    }
 
    static boolean [] SieveOfEratosthenes( int max_val)
    {
        // Create a boolean vector "prime[0..n]". A
        // value in prime[i] will finally be false
        // if i is Not a prime, else true.
        boolean [] prime = new boolean [max_val + 1 ];
        for ( int i = 0 ;i <= max_val ; i++)
        prime[i] = true ;
        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 ;
            }
        }
        return prime;
    }
 
    // Function that calculates the sum
    // and product of k smallest and k
    // largest prime numbers in an array
    static void primeSumAndProduct( int arr[], int n, int k)
    {
        // Find maximum value in the array
        int max_val = 0 ;
        for ( int i = 0 ; i < n; i++)
            max_val = Math.max(max_val, arr[i]);
 
        // Use sieve to find all prime numbers
        // less than or equal to max_val
        boolean [] prime = SieveOfEratosthenes(max_val);
 
        // Set 0 and 1 as non-primes as
        // they don't need to be
        // counted as prime numbers
        prime[ 0 ] = false ;
        prime[ 1 ] = false ;
 
        // Max Heap to store all the prime numbers
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
 
        // Min Heap to store all the prime numbers
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
 
        // Push all the prime numbers
        // from the array to the heaps
        for ( int i = 0 ; i < n; i++)
            if (prime[arr[i]]) {
                minHeap.add(arr[i]);
                maxHeap.add(arr[i]);
            }
 
        long minProduct = 1 , maxProduct = 1 , minSum = 0 , maxSum = 0 ;
        while (k > 0 )
        {
            k--;
             
            // Calculate the products
            minProduct *= minHeap.peek();
            maxProduct *= maxHeap.peek();
 
            // Calculate the sum
            minSum += minHeap.peek();
            maxSum += maxHeap.peek();
 
            // Pop the current minimum element
            minHeap.remove();
 
            // Pop the current maximum element
            maxHeap.remove();
        }
 
        System.out.println( "Sum of k-minimum prime numbers is " + minSum);
        System.out.println( "Sum of k-maximum prime numbers is " + maxSum);
        System.out.println( "Product of k-minimum prime numbers is " + minProduct);
        System.out.println( "Product of k-maximum prime numbers is " + maxProduct);
    }
 
}
 
// This code is contributed by ankush_953

Python3

 # Python program to find the sum
 # and product of k smallest and
 # k largest prime numbers in an array
 import heapq
 
def SieveOfEratosthenes(max_val):
    # Create a boolean vector "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 )]
    p = 2
    while p * p < = max_val:
        # If prime[p] is not changed, then
        # it is a prime
        if (prime[p] = = True ):
 
            # Update all multiples of p
            for j in range ( 2 * p,max_val + 1 ,p):
                prime[j] = False
        p + = 1
     
    return prime
 
# Function that calculates the sum
 # and product of k smallest and k
 # largest prime numbers in an array
 def primeSumAndProduct(arr, n, k):
    # Find maximum value in the array
    max_val = max (arr)
 
    # Use sieve to find all prime numbers
    # less than or equal to max_val
    prime = SieveOfEratosthenes(max_val)
 
    # Set 0 and 1 as non-primes as
    # they don't need to be
    # counted as prime numbers
    prime[ 0 ] = False
    prime[ 1 ] = False
 
    # Heap to store all the prime numbers
    Heap = []
 
    # Push all the prime numbers
    # from the array to the heaps
    for i in range (n):
        if (prime[arr[i]]):
            Heap.append(arr[i])
     
    minProduct = 1
    maxProduct = 1
    minSum = 0
    maxSum = 0
 
    min_k = heapq.nsmallest(k,Heap)
    max_k = heapq.nlargest(k,Heap)
 
    minSum = sum (min_k)
    maxSum = sum (max_k)
     
    for val in min_k:
        minProduct * = val
     
    for val in max_k:
        maxProduct * = val
     
    print ( "Sum of k-minimum prime numbers is" , minSum)
    print ( "Sum of k-maximum prime numbers is" , maxSum)
    print ( "Product of k-minimum prime numbers is" , minProduct)
    print ( "Product of k-maximum prime numbers is" , maxProduct)
 
# Driver code
 arr = [ 4 , 2 , 12 , 13 , 5 , 19 ]
 n = len (arr)
 k = 3
 primeSumAndProduct(arr, n, k)
 
# This code is contributed by ankush_953

Выход:

Сумма k-минимальных простых чисел равна 20
Сумма k-максимальных простых чисел равна 37
Произведение k-минимальных простых чисел равно 130
Произведение k-максимальных простых чисел равно 1235.

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Technical Scripter Олимпиады по программированию Структуры данных

Сумма и произведение k наименьших и k наибольших простых чисел в массиве

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

C ++

Джава

Python3

РЕКОМЕНДУЕМЫЕ СТАТЬИ