Given a positive integer N, the task is to find the Nth Composite Number.
Examples:
Input: N = 1
Output: 4Input: 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 105 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 Nth 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 Eratosthenesint 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 Codeint main(){ int N = 4; cout << NthComposite(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class GFG {// Function to find the Nth Composite// Numbers using Sieve of Eratosthenespublic 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 Eratosthenesdef 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 Codeif __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 approachlet MAX_SIZE = 1000005;// Function to find the Nth Composite// Numbers using Sieve of Eratosthenesfunction 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 Codelet N = 4;document.write(NthComposite(N));</script> |
Output
9
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 compositebool 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 approachint 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 approachdef is_composite(n): for i in range(2, int(n ** 0.5) + 1): if n % i == 0: return True return Falsedef 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 = 3print("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 compositefunction 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 approachfunction 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 = 3console.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)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Read More on on that Topic: geeksforgeeks.org/program-to-find-the-nth-composite-number/ […]
… [Trackback]
[…] Read More on on that Topic: geeksforgeeks.org/program-to-find-the-nth-composite-number/ […]
… [Trackback]
[…] Info to that Topic: geeksforgeeks.org/program-to-find-the-nth-composite-number/ […]
… [Trackback]
[…] Read More Information here on that Topic: geeksforgeeks.org/program-to-find-the-nth-composite-number/ […]
… [Trackback]
[…] Find More on on that Topic: geeksforgeeks.org/program-to-find-the-nth-composite-number/ […]