Count of sets possible using integers from a range [ 2 , N ] using given operations that are in Equivalence Relation | Python3 program for the above approach ; Sieve of Eratosthenes to find primes less than or equal to N ; Function to find number of Sets ; Handle Base Case ; Set which contains less than or equal to N / 2 ; Number greater than N / 2 and are prime increment it by 1 ; If the number is prime Increment answer by 1 ; Driver Code ; Input ; Function Call
prime = [ True ] * 100001 NEW_LINE def SieveOfEratosthenes ( n ) : NEW_LINE INDENT global prime NEW_LINE for p in range ( 2 , n + 1 ) : NEW_LINE INDENT if p * p > n : NEW_LINE INDENT break NEW_LINE DEDENT if ( prime [ p ] == True ) : NEW_LINE INDENT for i in range ( p * p , n + 1 , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT DEDENT DEDENT def NumberofSets ( N ) : NEW_LINE INDENT SieveOfEratosthenes ( N ) NEW_LINE if ( N == 2 ) : NEW_LINE INDENT print ( 1 ) NEW_LINE DEDENT elif ( N == 3 ) : NEW_LINE INDENT print ( 2 ) NEW_LINE DEDENT else : NEW_LINE INDENT ans = 1 NEW_LINE for i in range ( N // 2 , N + 1 ) : NEW_LINE INDENT if ( prime [ i ] ) : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT DEDENT print ( ans ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 9 NEW_LINE NumberofSets ( N ) NEW_LINE DEDENT