Given an array arr of size N. The task is to find the prime numbers in the first half (up to index N/2) and the second half (all the remaining elements) of an array.
Examples:
Input : arr[] = {2, 5, 10, 15, 17, 21, 23 }
Output :2 5 and 17 23
Prime numbers in the first half of an array are 2, 5 and in the second half are 17, 23
Input : arr[] = {31, 35, 40, 43}
Output :31 and 43
Approach:
First Traverse the array up to N/2 and check all the elements whether they are prime or not and print the prime numbers. Then Traverse the array from N/2th element till N and find whether elements are prime or not and print all those elements which are prime.
Below is the implementation of the above approach:
C++
// C++ program to print the prime numbers in the// first half and second half of an array#include <bits/stdc++.h>using namespace std;// Function to check if a number is prime or notbool prime(int n){ for (int i = 2; i * i <= n; i++) if (n % i == 0) return false; return true;}// Function to find whether elements are prime or notvoid prime_range(int start, int end, int* a){ // Traverse in the given range for (int i = start; i < end; i++) { // Check if a number is prime or not if (prime(a[i])) cout << a[i] << " "; }}// Function to print the prime numbers in the// first half and second half of an arrayvoid Print(int arr[], int n){ cout << "Prime numbers in the first half are "; prime_range(0, n / 2, arr); cout << endl; cout << "Prime numbers in the second half are "; prime_range(n / 2, n, arr); cout << endl;}// Driver Codeint main(){ int arr[] = { 2, 5, 10, 15, 17, 21, 23 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call Print(arr, n); return 0;} |
Java
// Java program to print the prime numbers in the // first half and second half of an arrayimport java.util.*;class GFG {// Function to check if // a number is prime or notstatic boolean prime(int n){ for(int i = 2; i * i <= n; i++) if(n % i == 0) return false; return true;}// Function to find whether elements// are prime or notstatic void prime_range(int start, int end, int[] a){ // Traverse in the given range for (int i = start; i < end; i++) { // Check if a number is prime or not if(prime(a[i])) System.out.print(a[i] + " "); }}// Function to print the prime numbers in the // first half and second half of an arraystatic void Print(int arr[], int n){ System.out.print("Prime numbers in the first half are "); prime_range(0, n / 2, arr); System.out.println(); System.out.print("Prime numbers in the second half are "); prime_range(n / 2, n, arr); System.out.println();}// Driver Codepublic static void main(String[] args) { int arr[] = { 2, 5, 10, 15, 17, 21, 23 }; int n = arr.length; // Function call Print(arr, n);}}// This code is contributed by Princi Singh |
Python3
# Python3 program to print the # prime numbers in the first half # and second half of an array# Function to check if # a number is prime or notdef prime(n): for i in range(2, n): if i * i > n: break if(n % i == 0): return False; return True # Function to find whether # elements are prime or notdef prime_range(start, end, a): # Traverse in the given range for i in range(start, end): # Check if a number is prime or not if(prime(a[i])): print(a[i], end = " ")# Function to print the # prime numbers in the first half# and second half of an arraydef Print(arr, n): print("Prime numbers in the", "first half are ", end = "") prime_range(0, n // 2, arr) print() print("Prime numbers in the", "second half are ", end = "") prime_range(n // 2, n, arr) print()# Driver Codearr = [2, 5, 10, 15, 17, 21, 23]n = len(arr)# Function callPrint(arr, n)# This code is contributed # by Mohit Kumar |
C#
// C# program to print the prime numbers in the // first half and second half of an arrayusing System; class GFG {// Function to check if // a number is prime or notstatic Boolean prime(int n){ for(int i = 2; i * i <= n; i++) if(n % i == 0) return false; return true;}// Function to find whether elements// are prime or notstatic void prime_range(int start, int end, int[] a){ // Traverse in the given range for (int i = start; i < end; i++) { // Check if a number is prime or not if(prime(a[i])) Console.Write(a[i] + " "); }}// Function to print the prime numbers in the // first half and second half of an arraystatic void Print(int []arr, int n){ Console.Write("Prime numbers in the first half are "); prime_range(0, n / 2, arr); Console.WriteLine(); Console.Write("Prime numbers in the second half are "); prime_range(n / 2, n, arr); Console.WriteLine();}// Driver Codepublic static void Main(String[] args) { int []arr = { 2, 5, 10, 15, 17, 21, 23 }; int n = arr.Length; // Function call Print(arr, n);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to print the prime numbers in the// first half and second half of an array// Function to check if a number is prime or notfunction prime(n){ for (let i = 2; i * i <= n; i++) if (n % i == 0) return false; return true;}// Function to find whether elements are prime or notfunction prime_range(start, end, a){ // Traverse in the given range for (let i = start; i < end; i++) { // Check if a number is prime or not if (prime(a[i])) document.write(a[i] + " "); }}// Function to print the prime numbers in the// first half and second half of an arrayfunction Print(arr, n){ document.write("Prime numbers in the first half are "); prime_range(0, parseInt(n / 2), arr); document.write("<br>"); document.write("Prime numbers in the second half are "); prime_range(parseInt(n / 2), n, arr); document.write("<br>");}// Driver Codelet arr = [ 2, 5, 10, 15, 17, 21, 23 ];let n = arr.length;// Function callPrint(arr, n);// This code is contributed by rishavmahato348.</script> |
Output:
Prime numbers in the first half are 2 5 Prime numbers in the second half are 17 23
Time Complexity: O(n * sqrt(n)), as we are using a loop for traversing n times and each time for checking if a number is prime or not we are using a loop to traverse sqrt(n) times which will cost O(sqrt(n)).
Auxiliary Space: O(1), as we are not using any extra space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
