Smallest composite number not divisible by first N prime numbers

0 0 5 minutes read

Given an integer N, the task is to find the smallest composite number which is not divisible by first N prime numbers.

Examples:

Input: N = 3
Output: 49
Explanation:
The first 3 prime numbers are {2, 3, 5}. The smallest composite integer not divisible by either 2, 3, or 5 is 49.

Input: N = 2
Output: 25
Explanation:
The first 2 prime numbers are {2, 3}. The smallest composite integer not divisible by either 2 or 3 is 25.

Naive Approach: The simplest approach to solve the problem is to check the below conditions for each number starting from 2:

Condition 1: Check if the current number is prime or not. If prime, then repeat the process for next number. Else, if the number is composite, then check the below conditions:
Condition 2: Find the first N prime numbers and check if this composite number is not divisible by each of them.
If the current number satisfies both the above conditions, then print that number as the required answer.

Time Complexity: O(M³N), where M denotes the composite number satisfying the condition.
Auxiliary Space: O(N), to store the N prime numbers.

Efficient Approach: The given problem can be solved using the following observation:

The first composite number which is not divisible by any of the first N prime numbers = ((N + 1)^th prime number)²

Illustration:

For N = 2
=> The first 2 prime numbers are {2, 3}
=> (N + 1)^th prime number is 5
=> It can be observed that all the non prime numbers up to 24 {4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24} are divisible by either 2, or 3, or both.
=> The next composite number {25} is divisible by 5 only.
=> Therefore, it can be concluded that the first composite number which is not divisible by any of the first N prime numbers is the square of the (N + 1)^th prime number.

The idea is to find the (N+1)^th prime number using Sieve of Eratosthenes and print the square of the (N+1)^th prime number as the answer.

Below is the implementation of the above approach:

C++

// C++ Program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Initializing the max value
#define MAX_SIZE 1000005
 
// Function to generate N prime numbers
// using Sieve of Eratosthenes
void SieveOfEratosthenes(
    vector<int>& StorePrimes)
{
    // Stores the primes
    bool IsPrime[MAX_SIZE];
 
    // Setting all numbers to be prime initially
    memset(IsPrime, true, sizeof(IsPrime));
 
    for (int p = 2; p * p < MAX_SIZE; p++) {
 
        // If a prime number is encountered
        if (IsPrime[p] == true) {
 
            // Set all its multiples as composites
            for (int i = p * p; i < MAX_SIZE; i += p)
                IsPrime[i] = false;
        }
    }
 
    // Store all the prime numbers
    for (int p = 2; p < MAX_SIZE; p++)
        if (IsPrime[p])
            StorePrimes.push_back(p);
}
 
// Function to find the square of
// the (N + 1)-th prime number
int Smallest_non_Prime(
    vector<int> StorePrimes,
    int N)
{
    int x = StorePrimes[N];
    return x * x;
}
 
// Driver Code
int main()
{
    int N = 3;
 
    // Stores all prime numbers
    vector<int> StorePrimes;
 
    SieveOfEratosthenes(StorePrimes);
 
    cout << Smallest_non_Prime(StorePrimes, N);
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.Arrays;
import java.util.Vector;
 
class GFG{
 
// Initializing the max value
static final int MAX_SIZE = 1000005;
 
// Function to generate N prime numbers
// using Sieve of Eratosthenes
static void SieveOfEratosthenes(
    Vector<Integer> StorePrimes)
{
     
    // Stores the primes
    boolean []IsPrime = new boolean[MAX_SIZE];
 
    // Setting all numbers to be prime initially
    Arrays.fill(IsPrime, true);
 
    for(int p = 2; p * p < MAX_SIZE; p++) 
    {
         
        // If a prime number is encountered
        if (IsPrime[p] == true) 
        {
             
            // Set all its multiples as composites
            for(int i = p * p; i < MAX_SIZE; i += p)
                IsPrime[i] = false;
        }
    }
 
    // Store all the prime numbers
    for(int p = 2; p < MAX_SIZE; p++)
        if (IsPrime[p])
            StorePrimes.add(p);
}
 
// Function to find the square of
// the (N + 1)-th prime number
static int Smallest_non_Prime(
    Vector<Integer> StorePrimes,
    int N)
{
    int x = StorePrimes.get(N);
    return x * x;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 3;
 
    // Stores all prime numbers
    Vector<Integer> StorePrimes = new Vector<Integer>();
 
    SieveOfEratosthenes(StorePrimes);
 
    System.out.print(Smallest_non_Prime(StorePrimes, N));
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program to implement
# the above approach
 
# Initializing the max value
MAX_SIZE = 1000005
 
# Function to generate N prime numbers
# using Sieve of Eratosthenes
def SieveOfEratosthenes(StorePrimes):
     
    # Stores the primes
    IsPrime = [True for i in range(MAX_SIZE)]
 
    p = 2
    while (p * p < MAX_SIZE):
         
        # If a prime number is encountered
        if (IsPrime[p] == True):
             
            # Set all its multiples as composites
            for i in range(p * p, MAX_SIZE, p):
                IsPrime[i] = False
                 
        p += 1
 
    # Store all the prime numbers
    for p in range(2, MAX_SIZE):
        if (IsPrime[p]):
            StorePrimes.append(p)
 
# Function to find the square of
# the (N + 1)-th prime number
def Smallest_non_Prime(StorePrimes, N):
     
    x = StorePrimes[N]
     
    return x * x
 
# Driver Code
if __name__ == '__main__':
     
    N = 3
 
    # Stores all prime numbers
    StorePrimes = []
 
    SieveOfEratosthenes(StorePrimes)
 
    print(Smallest_non_Prime(StorePrimes, N))
 
# This code is contributed by bgangwar59

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Initializing the max value
static readonly int MAX_SIZE = 1000005;
 
// Function to generate N prime numbers
// using Sieve of Eratosthenes
static void SieveOfEratosthenes(
    List<int> StorePrimes)
{
     
    // Stores the primes
    bool []IsPrime = new bool[MAX_SIZE];
 
    // Setting all numbers to be prime initially
    for(int i = 0; i < MAX_SIZE; i++)
        IsPrime[i] = true;
 
    for(int p = 2; p * p < MAX_SIZE; p++) 
    {
         
        // If a prime number is encountered
        if (IsPrime[p] == true) 
        {
             
            // Set all its multiples as composites
            for(int i = p * p; i < MAX_SIZE; i += p)
                IsPrime[i] = false;
        }
    }
 
    // Store all the prime numbers
    for(int p = 2; p < MAX_SIZE; p++)
        if (IsPrime[p])
            StorePrimes.Add(p);
}
 
// Function to find the square of
// the (N + 1)-th prime number
static int Smallest_non_Prime(
    List<int> StorePrimes,
    int N)
{
    int x = StorePrimes[N];
    return x * x;
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 3;
 
    // Stores all prime numbers
    List<int> StorePrimes = new List<int>();
 
    SieveOfEratosthenes(StorePrimes);
 
    Console.Write(Smallest_non_Prime(StorePrimes, N));
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// Javascript Program to implement
// the above approach
 
// Initializing the max value
var MAX_SIZE = 1000005;
 
// Function to generate N prime numbers
// using Sieve of Eratosthenes
function SieveOfEratosthenes(StorePrimes)
{
    // Stores the primes
    var IsPrime = Array(MAX_SIZE).fill(true);
     
    var p,i;
    for(p = 2; p * p < MAX_SIZE; p++) {
 
        // If a prime number is encountered
        if (IsPrime[p] == true) {
 
            // Set all its multiples as composites
            for(i = p * p; i < MAX_SIZE; i += p)
                IsPrime[i] = false;
        }
    }
 
    // Store all the prime numbers
    for (p = 2; p < MAX_SIZE; p++)
        if (IsPrime[p])
            StorePrimes.push(p);
}
 
// Function to find the square of
// the (N + 1)-th prime number
function Smallest_non_Prime(StorePrimes, N)
{
    var x = StorePrimes[N];
    return x * x;
}
 
// Driver Code
    N = 3;
 
    // Stores all prime numbers
    var StorePrimes = [];
 
    SieveOfEratosthenes(StorePrimes);
 
    document.write(Smallest_non_Prime(StorePrimes, N));
 
</script>

Output:

Time Complexity: O(MAX_SIZE log (log MAX_SIZE)), where MAX_SIZE denotes the upper bound upto which N primes are generated.
Auxiliary Space: O(MAX_SIZE)

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!