text: Segregate Prime and Non | Java 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 ^ ; 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: import java . util . * ; class GFG { public static void SieveOfEratosthenes ( boolean [ ] prime , int n ) { for ( int p = 2 ; p * p <= n ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i <= n ; i += p ) prime [ i ] = false ; } } } public static void segregatePrimeNonPrime ( boolean [ ] prime , int arr [ ] , int N ) { SieveOfEratosthenes ( prime , 10000000 ) ; int left = 0 , right = N - 1 ; while ( left < right ) { while ( prime [ arr [ left ] ] ) left ++ ; while ( ! prime [ arr [ right ] ] ) right -- ; if ( left < right ) { int temp = arr [ left ] ; arr [ left ] = arr [ right ] ; arr [ right ] = temp ; left ++ ; right -- ; } } for ( int i = 0 ; i < N ; i ++ ) System . out . printf ( arr [ i ] + " ▁ " ) ; } public static void main ( String [ ] args ) { boolean [ ] prime = new boolean [ 10000001 ] ; Arrays . fill ( prime , true ) ; int arr [ ] = { 2 , 3 , 4 , 6 , 7 , 8 , 9 , 10 } ; int N = arr . length ; segregatePrimeNonPrime ( prime , arr , N ) ; } }