Program to find the Nth Composite Number

0 0 7 minutes read

Given a positive integer N, the task is to find the N^th Composite Number.

Examples:

Input: N = 1
Output: 4

Input: N = 3
Output: 8

Approach: The given problem can be solved by using the concept of Sieve of Eratosthenes. Follow the steps below to solve the problem:

Mark all the Prime Numbers till 10⁵ in a boolean array say isPrime[] using Sieve of Eratosthenes.
Initialize an array, say composites[] that stores all the composite numbers.
Traverse the array isPrime[] using the variable i, if the value of isPrime[i] is false, then insert the number i in the array composites[].
After completing the above steps, print the value composites[N – 1] as the N^th Composite Number.

Below is the implementation of the above approach:

C++

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

Java

// Java program for the above approach
import java.util.*;
public class GFG 
{
 
// Function to find the Nth Composite
// Numbers using Sieve of Eratosthenes
public static int NthComposite(int N)
{
    int MAX_SIZE = 1000005;
   
    // Sieve of prime numbers
    boolean[] IsPrime = new boolean[MAX_SIZE];
 
    // Initialize the array to true
    Arrays.fill(IsPrime, true);
 
    // Iterate over the range [2, MAX_SIZE]
    for (int p = 2; p * p < MAX_SIZE; p++) {
 
        // If IsPrime[p] is true
        if (IsPrime[p] == true) {
 
            // Iterate over the
            // range [p * p, MAX_SIZE]
            for (int i = p * p;
                 i < MAX_SIZE; i += p)
                IsPrime[i] = false;
        }
    }
 
    // Stores the list of composite numbers
    Vector<Integer> Composites = new Vector<Integer>();
 
    // Iterate over the range [4, MAX_SIZE]
    for (int p = 4; p < MAX_SIZE; p++)
 
        // If i is not prime
        if (!IsPrime[p])
            Composites.add(p);
 
    // Return Nth Composite Number
    return Composites.get(N - 1);
}
 
// Driver Code
   public static void main(String args[]) 
   {
     int N = 4;
     System.out.println(NthComposite(N));
    }
}
 
// This code is contributed by SoumikMondal.

Python3

# Python3 program for the above approach
 
# Function to find the Nth Composite
# Numbers using Sieve of Eratosthenes
def NthComposite(N):
   
    # Sieve of prime numbers
    IsPrime = [True]*1000005
 
    # Iterate over the range [2, 1000005]
    for p in range(2, 1000005):
        if p * p > 1000005:
            break
 
        # If IsPrime[p] is true
        if (IsPrime[p] == True):
           
            # Iterate over the
            # range [p * p, 1000005]
            for i in range(p*p,1000005,p):
                IsPrime[i] = False
 
    # Stores the list of composite numbers
    Composites = []
 
    # Iterate over the range [4, 1000005]
    for p in range(4,1000005):
 
        # If i is not prime
        if (not IsPrime[p]):
            Composites.append(p)
 
    # Return Nth Composite Number
    return Composites[N - 1]
 
# Driver Code
if __name__ == '__main__':
    N = 4
    print (NthComposite(N))
 
# This code is contributed by mohit kumar 29.

C#

using System;
using System.Collections.Generic;
 
public class GFG{
 
  // Function to find the Nth Composite
  // Numbers using Sieve of Eratosthenes
  public static int NthComposite(int N)
  {
    int MAX_SIZE = 1000005;
 
    // Sieve of prime numbers
    bool[] IsPrime = new bool[MAX_SIZE];
 
    // Initialize the array to true
    Array.Fill(IsPrime, true);
 
    // Iterate over the range [2, MAX_SIZE]
    for (int p = 2; p * p < MAX_SIZE; p++) {
 
      // If IsPrime[p] is true
      if (IsPrime[p] == true) {
 
        // Iterate over the
        // range [p * p, MAX_SIZE]
        for (int i = p * p;
             i < MAX_SIZE; i += p)
          IsPrime[i] = false;
      }
    }
 
    // Stores the list of composite numbers
    List<int> Composites = new List<int>();
 
    // Iterate over the range [4, MAX_SIZE]
    for (int p = 4; p < MAX_SIZE; p++)
 
      // If i is not prime
      if (!IsPrime[p])
        Composites.Add(p);
 
    // Return Nth Composite Number
    return Composites[N - 1];
  }
 
  // Driver Code
  static public void Main ()
  {
 
    int N = 4;
    Console.WriteLine(NthComposite(N));
 
  }
}
 
// This code is contributed by patel2127

Javascript

<script>
 
// JavaScript program for the above approach
 
let MAX_SIZE =  1000005;
 
// Function to find the Nth Composite
// Numbers using Sieve of Eratosthenes
function NthComposite( N)
{
    // Sieve of prime numbers
    let IsPrime = [];
 
    // Initialize the array to true
    for(let i = 0;i<MAX_SIZE;i++)
        IsPrime.push(true);
 
    // Iterate over the range [2, MAX_SIZE]
    for (let p = 2;
         p * p < MAX_SIZE; p++) {
 
        // If IsPrime[p] is true
        if (IsPrime[p] == true) {
 
            // Iterate over the
            // range [p * p, MAX_SIZE]
            for (let i = p * p;
                 i < MAX_SIZE; i += p)
                IsPrime[i] = false;
        }
    }
 
    // Stores the list of composite numbers
    let Composites = [];
 
    // Iterate over the range [4, MAX_SIZE]
    for (let p = 4; p < MAX_SIZE; p++)
 
        // If i is not prime
        if (!IsPrime[p])
            Composites.push(p);
 
    // Return Nth Composite Number
    return Composites[N - 1];
}
 
// Driver Code
let N = 4;
document.write(NthComposite(N));
 
</script>

Output

Time Complexity: O(N + M * log(log(M)), where [2, M] is the range where Sieve of Eratosthenes is performed.
Auxiliary Space: O(N)

Program to find the Nth Composite Number in python using Brute Force approach

Example 2: By using Brute Force approach

Approach:

Define a function is_composite(n) that takes a number n as input and returns True if n is composite (i.e., has a factor other than 1 and itself), and False otherwise. This function checks for factors by iterating from 2 to the square root of n, and returning True if any of these numbers divides n evenly.
Define a function nth_composite_brute_force(n) that takes an integer n as input and returns the n-th composite number. The function initializes a counter count to 0, and a number num to 4 (since 4 is the smallest composite number).
The function then enters a loop that continues until count is equal to n. Within the loop, the function checks if num is composite by calling the is_composite function. If num is composite, the function increments count by 1.
Regardless of whether num is composite or not, the function increments num by 1 and continues to the next iteration of the loop.
When the loop exits (i.e., when count is equal to n), the function returns the value of num minus 1 (since the loop incremented num one too many times).
Overall, this approach checks every number starting from 4 until it finds the n-th composite number. Since it checks each number up to its square root, the time complexity of the is_composite function is O(sqrt(n)). Since we call this function for every number from 4 to the n-th composite number, the total time complexity of this approach is O(n^2 * sqrt(n)). The space complexity is O(1), since we only store a counter and a single number.

C++

#include <iostream>
#include <cmath>
 
using namespace std; // Add this line to use the std namespace
 
// Function to check if a number is composite
bool isComposite(int n) {
    for (int i = 2; i <= sqrt(n); ++i) {
        if (n % i == 0) {
            return true;
        }
    }
    return false;
}
 
// Function to find the nth composite number using a brute force approach
int nthCompositeBruteForce(int n) {
    int count = 0;
    int num = 4;
    while (count < n) {
        if (isComposite(num)) {
            count++;
        }
        num++;
    }
    return num - 1;
}
 
int main() {
    // Test the function with N = 1 and N = 3
    cout << "N = 1, Output = " << nthCompositeBruteForce(1) << endl;
    cout << "N = 3, Output = " << nthCompositeBruteForce(3) << endl;
 
    return 0;
}

Java

import java.util.Scanner;
 
public class Main {
    // Function to check if a number is composite
    static boolean isComposite(int n) {
        for (int i = 2; i <= Math.sqrt(n); ++i) {
            if (n % i == 0) {
                return true;
            }
        }
        return false;
    }
 
    // Function to find the nth composite number using a brute-force approach
    static int nthCompositeBruteForce(int n) {
        int count = 0;
        int num = 4;
        while (count < n) {
            if (isComposite(num)) {
                count++;
            }
            num++;
        }
        return num - 1;
    }
 
    public static void main(String[] args) {
        // Test the function with N = 1 and N = 3
        System.out.println("N = 1, Output = " + nthCompositeBruteForce(1));
        System.out.println("N = 3, Output = " + nthCompositeBruteForce(3));
    }
}

Python3

import time
 
# Brute Force approach
def is_composite(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return True
    return False
 
def nth_composite_brute_force(n):
    count = 0
    num = 4
    while count < n:
        if is_composite(num):
            count += 1
        num += 1
    return num - 1
 
# Test the function with N = 1 and N = 3
print("N = 1, Output = ", nth_composite_brute_force(1))
 
print("N = 3, Output = ", nth_composite_brute_force(3))

Javascript

//Javascript code for the above approach
 
// Function to check if a number is composite
function isComposite(n) {
    for (let i = 2; i <= Math.sqrt(n); ++i) {
        if (n % i === 0) {
            return true;
        }
    }
    return false;
}
 
// Function to find the nth composite number using a brute force approach
function nthCompositeBruteForce(n) {
    let count = 0;
    let num = 4;
    while (count < n) {
        if (isComposite(num)) {
            count++;
        }
        num++;
    }
    return num - 1;
}
 
// Test the function with N = 1 and N = 3
console.log("N = 1, Output = " + nthCompositeBruteForce(1));
console.log("N = 3, Output = " + nthCompositeBruteForce(3));

Output

N = 1, Output =  4
N = 3, Output =  8

Time Complexity: O(N^2 * logN)
Space Complexity: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!