Сумма и произведение k наименьших и k наибольших простых чисел в массиве
Учитывая целое число 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 и многому другому, см. Полный курс подготовки к собеседованию .