Given a positive integer N, the task is to find the smallest semi-prime number such that the difference between any of its two divisors is at least N.
Examples:
Input: N = 2
Output: 15
Explanation:
The divisors of 15 are 1, 3, 5, and 15 and the difference between any of its two divisors is greater than or equal to N(= 2).Input: N = 3
Output: 55
Approach: The given problem can be solved by finding two prime numbers(say X and Y) whose difference is at least N. The idea is to find the first prime number i.e., X greater than N, and the second prime number i.e., Y greater than (N + X). Follow the steps below to solve the problem:
- Initialize a boolean array prime[] to store the prime numbers up to 105 using Sieve of Eratosthenes such that if i is prime, then prime[i] will be true. Otherwise, false.
- Initialize two variables, say X and Y that stores both the prime numbers such that the product of X and Y is the resultant semi-prime number.
- Iterate a loop from (N + 1) using the variable i and if the value of prime[i] is true, then update the value of X as i and break out of the loop.
- Iterate a loop from (N + X) using the variable i and if the value of prime[i] is true, then update the value of Y as i and break out of the loop.
- After completing the above steps, print the product of X and Y as the resulting semi-prime number.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>#define MAX 100001using namespace std;// Function to find all the prime// numbers using Sieve of Eratosthenesvoid SieveOfEratosthenes(bool prime[]){ // Set 0 and 1 as non-prime prime[0] = false; prime[1] = false; for (int p = 2; p * p < MAX; p++) { // If p is a prime if (prime[p] == true) { // Set all multiples // of p as non-prime for (int i = p * p; i < MAX; i += p) prime[i] = false; } }}// Function to find the smallest semi-prime// number having a difference between any// of its two divisors at least Nvoid smallestSemiPrime(int n){ // Stores the prime numbers bool prime[MAX]; memset(prime, true, sizeof(prime)); // Fill the prime array SieveOfEratosthenes(prime); // Initialize the first divisor int num1 = n + 1; // Find the value of the first // prime number while (prime[num1] != true) { num1++; } // Initialize the second divisor int num2 = num1 + n; // Find the second prime number while (prime[num2] != true) { num2++; } // Print the semi-prime number cout << num1 * 1LL * num2;}// Driver Codeint main(){ int N = 2; smallestSemiPrime(N); return 0;} |
Java
// Java approach for the above approachclass GFG{static int MAX = 100001;// Function to find all the prime// numbers using Sieve of Eratosthenesstatic void SieveOfEratosthenes(boolean prime[]){ // Set 0 and 1 as non-prime prime[0] = false; prime[1] = false; for(int p = 2; p * p < MAX; p++) { // If p is a prime if (prime[p] == true) { // Set all multiples // of p as non-prime for(int i = p * p; i < MAX; i += p) prime[i] = false; } }}// Function to find the smallest semi-prime// number having a difference between any// of its two divisors at least Nstatic void smallestSemiPrime(int n){ // Stores the prime numbers boolean[] prime = new boolean[MAX]; for(int i = 0; i < prime.length; i++) { prime[i] = true; } // Fill the prime array SieveOfEratosthenes(prime); // Initialize the first divisor int num1 = n + 1; // Find the value of the first // prime number while (prime[num1] != true) { num1++; } // Initialize the second divisor int num2 = num1 + n; // Find the second prime number while (prime[num2] != true) { num2++; } // Print the semi-prime number System.out.print(num1 * num2);}// Driver Codepublic static void main(String[] args){ int N = 2; smallestSemiPrime(N);}}// This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approachMAX = 100001# Function to find all the prime# numbers using Sieve of Eratosthenesdef SieveOfEratosthenes(prime): # Set 0 and 1 as non-prime prime[0] = False prime[1] = False p = 2 while p * p < MAX: # If p is a prime if (prime[p] == True): # Set all multiples # of p as non-prime for i in range(p * p, MAX, p): prime[i] = False p += 1# Function to find the smallest semi-prime# number having a difference between any# of its two divisors at least Ndef smallestSemiPrime(n): # Stores the prime numbers prime = [True] * MAX # Fill the prime array SieveOfEratosthenes(prime) # Initialize the first divisor num1 = n + 1 # Find the value of the first # prime number while (prime[num1] != True): num1 += 1 # Initialize the second divisor num2 = num1 + n # Find the second prime number while (prime[num2] != True): num2 += 1 # Print the semi-prime number print(num1 * num2)# Driver Codeif __name__ == "__main__": N = 2 smallestSemiPrime(N)# This code is contributed by ukasp |
C#
// C# program for the above approachusing System;class GFG{ static int MAX = 100001;// Function to find all the prime// numbers using Sieve of Eratosthenesstatic void SieveOfEratosthenes(bool[] prime){ // Set 0 and 1 as non-prime prime[0] = false; prime[1] = false; for(int p = 2; p * p < MAX; p++) { // If p is a prime if (prime[p] == true) { // Set all multiples // of p as non-prime for(int i = p * p; i < MAX; i += p) prime[i] = false; } }}// Function to find the smallest semi-prime// number having a difference between any// of its two divisors at least Nstatic void smallestSemiPrime(int n){ // Stores the prime numbers bool[] prime = new bool[MAX]; for(int i = 0; i < prime.Length; i++) { prime[i] = true; } // Fill the prime array SieveOfEratosthenes(prime); // Initialize the first divisor int num1 = n + 1; // Find the value of the first // prime number while (prime[num1] != true) { num1++; } // Initialize the second divisor int num2 = num1 + n; // Find the second prime number while (prime[num2] != true) { num2++; } // Print the semi-prime number Console.Write(num1 * num2);}// Driver codestatic void Main() { int N = 2; smallestSemiPrime(N);}}// This code is contributed by abhinavjain194 |
Javascript
<script>// JavaScript program to implement// the above approachlet MAX = 100001; // Function to find all the prime// numbers using Sieve of Eratosthenesfunction SieveOfEratosthenes(prime){ // Set 0 and 1 as non-prime prime[0] = false; prime[1] = false; for(let p = 2; p * p < MAX; p++) { // If p is a prime if (prime[p] == true) { // Set all multiples // of p as non-prime for(let i = p * p; i < MAX; i += p) prime[i] = false; } }} // Function to find the smallest semi-prime// number having a difference between any// of its two divisors at least Nfunction smallestSemiPrime(n){ // Stores the prime numbers let prime = Array.from({length: MAX}, (_, i) => 0); for(let i = 0; i < prime.length; i++) { prime[i] = true; } // Fill the prime array SieveOfEratosthenes(prime); // Initialize the first divisor let num1 = n + 1; // Find the value of the first // prime number while (prime[num1] != true) { num1++; } // Initialize the second divisor let num2 = num1 + n; // Find the second prime number while (prime[num2] != true) { num2++; } // Print the semi-prime number document.write(num1 * num2);}// Driver code let N = 2; smallestSemiPrime(N); // This code is contributed by code_hunt.</script> |
Output:
15
Time Complexity: O(M * log(log(M))), where M is the size of the prime[] array
Auxiliary Space: O(M)
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!
Share your thoughts in the comments
