Approach
We can approach this problem by using a concept called Sieve Of Eratosthenes. To learn more about Sieve Of Eratosthenes, visit What is the Sieve Method?
We will be using the fact that a number can be prime or composite. So all the numbers which are not prime are considered composite numbers.
Algorithm:
 Using the sieve of Eratosthenes, mark all the prime numbers up to the maximum limit, say 10^6, in an array called isPrime[].
 If isPrime[i] = 1, it means i is a prime number else not.
 Initialize an array that stores all the composite numbers.
 Let us call this array composites[].

Traverse isPrime[] using a forloop over i
 If isPrime[i]=false then it means it is a composite number, so insert it into composites[] array.
 Return composites[N1].
Code
#include<iostream>
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
//Program to find the Nth Composite Number
int NthComposite(int N)
{
// Sieve of eratosthenes.
bool IsPrime[1000000];
memset(IsPrime, true, sizeof(IsPrime));
for (int i = 2;i * i < 1000000; i++) {
if (IsPrime[i] == true) {
for (int j = i * i;j < 1000000; j += i)
IsPrime[j] = false;
}
}
// Array of composite numbers
vector<int> Composites;
for (int i = 2; i < 1000000; i++)
// If i is not prime
if (IsPrime[i]==false)
Composites.push_back(i);
// Return Nth Composite Number
return Composites[N  1];
}
// Driver Code
int main()
{
int N = 3;
cout << NthComposite(N);
return 0;
}
Output
8
Complexity Analysis
Time Complexity: O(N (log(log N)) where ‘N’ is the maximum limit taken, i.e 10^{6}
=> (N / 2) + (N / 3) + (N / 5) + (N / 7) + … + (N / P), [where ‘P’ is the highest prime, ‘P’ <= ‘N’]
=> N [(1 / 2) + (1 / 3) + (1 / 5) + (1 / 7) + … + (1 / P)]
=> N (log (log N))
[ (1 / 2) + (1 / 3) + (1 / 5) + (1 / 7) + … + (1 / P) ] = log(log(N)) since it is a harmonic progression of sum of primes.
Space Complexity: O(N) where N is the maximum limit taken, i.e., 10^{6}
We have to use an array, isPrime[] of size N to store whether the number is prime or not up to all numbers till N.
Frequently Asked Questions

What are composite numbers?
Composite numbers can be defined as positive numbers with more than two factors. For example, 4,6,8,9,12…

What are prime numbers?
Prime numbers are natural numbers greater than 1, with exactly two factors, 1 and the number itself. For example, 2,3,5,7,11,13…

What are the advantages of using the sieve of Eratosthenes?
It has low implementation and is an optimized and efficient algorithm for finding the prime numbers in a particular range.
Also Read  Strong number in c
Key Takeaways
Today we solved a problem based on the concept of Sieve of Eratosthenes. A number can either be prime or composite. So we used this approach so that all those numbers that are not prime can be considered composite.
To learn about the linear time sieve method in C and C++, you can have a look at the Sieve of Eratosthenes with Linear time complexity.
Happy Coding!