Count of sets possible using integers from a range [ 2 , N ] using given operations that are in Equivalence Relation | Java program for tha 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
import java . util . * ; class GFG { static boolean prime [ ] = new boolean [ 100001 ] ; static void SieveOfEratosthenes ( int n ) { Arrays . fill ( prime , true ) ; for ( int p = 2 ; p * p <= n ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i <= n ; i += p ) prime [ i ] = false ; } } } static void NumberofSets ( int N ) { SieveOfEratosthenes ( N ) ; if ( N == 2 ) { System . out . print ( 1 ) ; } else if ( N == 3 ) { System . out . print ( 2 ) ; } else { int ans = 1 ; for ( int i = N / 2 + 1 ; i <= N ; i ++ ) { if ( prime [ i ] ) { ans += 1 ; } } System . out . print ( ans ) ; } } public static void main ( String [ ] args ) { int N = 9 ; NumberofSets ( N ) ; } }