1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Code
3.2.
Output
3.3.
Complexity Analysis
3.3.1.
Time Complexity: O(N (log(log N)) where ‘N’ is the maximum limit taken, i.e 106
3.3.2.
Space Complexity: O(N) where N is the maximum limit taken, i.e., 106
4.
5.
Key Takeaways
Last Updated: Mar 27, 2024

# Program To Find The Nth Composite Number

Rhythm Jain
0 upvote

## Introduction

Today, we have a problem where we need to find the Nth Composite Number.

Composite numbers are positive numbers with more than two factors.

Without any further delays, let's move to our problem statement.

## Problem Statement

We have an integer N. Our task is to find the Nth Composite Number.

Example:

Assume we have the following integer as input:

Input:

3

Output:

8

Explanation:

Composite numbers in series are 4,6,8,9,10,12…

We can observe that the 3rd composite number is 8.

Also see, Euclid GCD Algorithm

## 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 106

=> (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., 106

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.

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!

Live masterclass