Program To Find The Nth Composite Number

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 for-loop over i
  • If isPrime[i]=false then it means it is a composite number, so insert it into composites[] array.
• Return composites[N-1].

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⁶

    => (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⁶

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

1. What are composite numbers?
   Composite numbers can be defined as positive numbers with more than two factors. For example, 4,6,8,9,12…
    
2. 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…
    
3. 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!