text: Segregate Prime and Non | C ++ program for the above approach ; Function to generate prime numbers using Sieve of Eratosthenes ; If prime [ p ] is unchanged , then it is a prime ; Update all multiples of p ; Function to segregate the primes and non - primes ; Generate all primes till 10 ^ 7 ; Initialize left and right ; Traverse the array ; Increment left while array element at left is prime ; Decrement right while array element at right is non - prime ; If left < right , then swap arr [ left ] and arr [ right ] ; Swap arr [ left ] and arr [ right ] ; Print segregated array ; Driver code ; Function Call
code: #include <bits/stdc++.h> NEW_LINE #include <iostream> NEW_LINE using namespace std ; bool prime [ 10000001 ] ; void swap ( int * a , int * b ) { int temp = * a ; * a = * b ; * b = temp ; } void SieveOfEratosthenes ( int n ) { memset ( prime , true , sizeof ( prime ) ) ; for ( int p = 2 ; p * p <= n ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i <= n ; i += p ) prime [ i ] = false ; } } } void segregatePrimeNonPrime ( int arr [ ] , int N ) { SieveOfEratosthenes ( 10000000 ) ; int left = 0 , right = N - 1 ; while ( left < right ) { while ( prime [ arr [ left ] ] ) left ++ ; while ( ! prime [ arr [ right ] ] ) right -- ; if ( left < right ) { swap ( & arr [ left ] , & arr [ right ] ) ; left ++ ; right -- ; } } for ( int i = 0 ; i < N ; i ++ ) cout << arr [ i ] << " ▁ " ; } int main ( ) { int arr [ ] = { 2 , 3 , 4 , 6 , 7 , 8 , 9 , 10 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; segregatePrimeNonPrime ( arr , N ) ; return 0 ; }