Program to find the Nth Composite Number | C ++ program for the above approach ; Function to find the Nth Composite Numbers using Sieve of Eratosthenes ; Sieve of prime numbers ; Initialize the array to true ; Iterate over the range [ 2 , MAX_SIZE ] ; If IsPrime [ p ] is true ; Iterate over the range [ p * p , MAX_SIZE ] ; Stores the list of composite numbers ; Iterate over the range [ 4 , MAX_SIZE ] ; If i is not prime ; Return Nth Composite Number ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX_SIZE  1000005 NEW_LINE int NthComposite ( int N ) { bool IsPrime [ MAX_SIZE ] ; memset ( IsPrime , true , sizeof ( IsPrime ) ) ; for ( int p = 2 ; p * p < MAX_SIZE ; p ++ ) { if ( IsPrime [ p ] == true ) { for ( int i = p * p ; i < MAX_SIZE ; i += p ) IsPrime [ i ] = false ; } } vector < int > Composites ; for ( int p = 4 ; p < MAX_SIZE ; p ++ ) if ( ! IsPrime [ p ] ) Composites . push_back ( p ) ; return Composites [ N - 1 ] ; } int main ( ) { int N = 4 ; cout << NthComposite ( N ) ; return 0 ; }