Count of sets possible using integers from a range [ 2 , N ] using given operations that are in Equivalence Relation | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool prime [ 100001 ] ; 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 NumberofSets ( int N ) { SieveOfEratosthenes ( N ) ; if ( N == 2 ) { cout << 1 << endl ; } else if ( N == 3 ) { cout << 2 << endl ; } else { int ans = 1 ; for ( int i = N / 2 + 1 ; i <= N ; i ++ ) { if ( prime [ i ] ) { ans += 1 ; } } cout << ans << endl ; } } int main ( ) { int N = 9 ; NumberofSets ( N ) ; return 0 ; }