Segregate Prime and Non | 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
def SieveOfEratosthenes ( prime , n ) : NEW_LINE INDENT p = 2 NEW_LINE while ( p * p <= n ) : NEW_LINE INDENT if ( prime [ p ] == True ) : NEW_LINE INDENT i = p * p NEW_LINE while ( i <= n ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE i += p NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT DEDENT def segregatePrimeNonPrime ( prime , arr , N ) : NEW_LINE INDENT SieveOfEratosthenes ( prime , 10000000 ) NEW_LINE left , right = 0 , N - 1 NEW_LINE while ( left < right ) : NEW_LINE INDENT while ( prime [ arr [ left ] ] ) : NEW_LINE INDENT left += 1 NEW_LINE DEDENT while ( not prime [ arr [ right ] ] ) : NEW_LINE INDENT right -= 1 NEW_LINE DEDENT if ( left < right ) : NEW_LINE INDENT arr [ left ] , arr [ right ] = arr [ right ] , arr [ left ] NEW_LINE left += 1 NEW_LINE right -= 1 NEW_LINE DEDENT DEDENT for num in arr : NEW_LINE INDENT print ( num , end = " ▁ " ) NEW_LINE DEDENT DEDENT arr = [ 2 , 3 , 4 , 6 , 7 , 8 , 9 , 10 ] NEW_LINE N = len ( arr ) NEW_LINE prime = [ True ] * 10000001 NEW_LINE segregatePrimeNonPrime ( prime , arr , N ) NEW_LINE