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(M3N), 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)2
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 Eratosthenesvoid 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 numberint Smallest_non_Prime( vector<int> StorePrimes, int N){ int x = StorePrimes[N]; return x * x;}// Driver Codeint 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 approachimport java.util.Arrays;import java.util.Vector;class GFG{// Initializing the max valuestatic final int MAX_SIZE = 1000005;// Function to generate N prime numbers// using Sieve of Eratosthenesstatic 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 numberstatic int Smallest_non_Prime( Vector<Integer> StorePrimes, int N){ int x = StorePrimes.get(N); return x * x;}// Driver Codepublic 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 valueMAX_SIZE = 1000005# Function to generate N prime numbers# using Sieve of Eratosthenesdef 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 numberdef Smallest_non_Prime(StorePrimes, N): x = StorePrimes[N] return x * x# Driver Codeif __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 approachusing System;using System.Collections.Generic;class GFG{// Initializing the max valuestatic readonly int MAX_SIZE = 1000005;// Function to generate N prime numbers// using Sieve of Eratosthenesstatic 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 numberstatic int Smallest_non_Prime( List<int> StorePrimes, int N){ int x = StorePrimes[N]; return x * x;}// Driver Codepublic 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 valuevar MAX_SIZE = 1000005;// Function to generate N prime numbers// using Sieve of Eratosthenesfunction 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 numberfunction 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> |
49
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)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
