Smallest number having only 4 divisors with difference between any two at most D

0 0 5 minutes read

Given the number D, find the smallest number N such that it has exactly four divisors and the difference between any two of them is greater than or equal to D.

Examples:

Input: 1
Output: 6
Explanation: 6 has four divisors 1, 2, 3, and 6.
Difference between any two of them is always greater or equal to 1.

Input: 2
Output: 15
Explanation: 15 has four divisors 1, 3, 5 and 15.
Difference between any two of them is always greater or equal to 2

Input: 3
Output: 55
Explanation: 55 has four divisors 1, 5, 11 and 55.
Difference between any two of them is always greater than 3.

Approach: It is obvious that ‘1’ and the number itself are the divisors of N. So the number which has exactly 4 divisors has its divisors as 1, a, b, a*b respectively. For the condition that it has exactly 4 divisors, both a and b must be prime. For the condition that the difference between any two of them should at least be D, start finding a from 1+d and check whether it is prime or not, If it is not prime then we will find the prime number just next to it. Similarly, start finding b from a + d and check whether it is prime or not, and do the same as done for finding a.

Below is the implementation of the above approach.

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
int next_prime(int x)
{
    // Edge case
    if (x == 1 || x == 2) {
        return 2;
    }
 
    // Checking if x is prime
    bool is_prime = false;
 
    // Loop until next prime is found
    while (!is_prime) {
        is_prime = true;
        for (int i = 2; i <= sqrt(x); i++) {
            if (x % i == 0) {
                is_prime = false;
            }
        }
        x++;
    }
    return x - 1;
}
 
// Function to find the number
int findN(int D)
{
    // Assuming 1+D as first required
    // divisor because it is
    // at distance D from 1
    int a = 1 + D;
 
    // Checking whether 1+D is prime or not
    // otherwise it will return prime number
    // just next to it
    a = next_prime(a);
 
    // Checking the same for next divisor
    int b = a + D;
    b = next_prime(b);
 
    int N = a * b;
    return N;
}
 
// Driver Code
int main()
{
    int D = 2;
 
    int ans = findN(D);
    cout << ans;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  static int next_prime(int x)
  {
    // Edge case
    if (x == 1 || x == 2) {
      return 2;
    }
 
    // Checking if x is prime
    Boolean is_prime = false;
 
    // Loop until next prime is found
    while (!is_prime) {
      is_prime = true;
      for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
          is_prime = false;
        }
      }
      x++;
    }
    return x - 1;
  }
 
  // Function to find the number
  static int findN(int D)
  {
    // Assuming 1+D as first required
    // divisor because it is
    // at distance D from 1
    int a = 1 + D;
 
    // Checking whether 1+D is prime or not
    // otherwise it will return prime number
    // just next to it
    a = next_prime(a);
 
    // Checking the same for next divisor
    int b = a + D;
    b = next_prime(b);
 
    int N = a * b;
    return N;
  }
 
  // Driver Code
  public static void main (String[] args) {
    int D = 2;
 
    int ans = findN(D);
    System.out.println(ans);
  }
}
 
// This code is contributed by hrithikgarg03188.

Python3

# Python code for the above approach
def next_prime(x):
   
    # Edge case
    if (x == 1 or x == 2):
        return 2
 
    # Checking if x is prime
    is_prime = False
 
    # Loop until next prime is found
    while (not is_prime):
        is_prime = True
        for i in range(2, int(x ** 0.5) + 1):
            if (x % i == 0):
                is_prime = False
 
        x += 1
 
    return x - 1
 
# Function to find the number
def findN(D):
 
    # Assuming 1+D as first required
    # divisor because it is
    # at distance D from 1
    a = 1 + D
 
    # Checking whether 1+D is prime or not
    # otherwise it will return prime number
    # just next to it
    a = next_prime(a)
 
    # Checking the same for next divisor
    b = a + D
    b = next_prime(b)
 
    N = a * b
    return N
 
# Driver Code
D = 2
 
ans = findN(D)
print(ans)
 
# This code is contributed by Saurabh Jaiswal

C#

// C# program for the above approach
using System;
class GFG {
 
  static int next_prime(int x)
  {
     
    // Edge case
    if (x == 1 || x == 2) {
      return 2;
    }
 
    // Checking if x is prime
    bool is_prime = false;
 
    // Loop until next prime is found
    while (!is_prime) {
      is_prime = true;
      for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
          is_prime = false;
        }
      }
      x++;
    }
    return x - 1;
  }
 
  // Function to find the number
  static int findN(int D)
  {
     
    // Assuming 1+D as first required
    // divisor because it is
    // at distance D from 1
    int a = 1 + D;
 
    // Checking whether 1+D is prime or not
    // otherwise it will return prime number
    // just next to it
    a = next_prime(a);
 
    // Checking the same for next divisor
    int b = a + D;
    b = next_prime(b);
 
    int N = a * b;
    return N;
  }
 
  // Driver Code
  public static void Main () {
    int D = 2;
 
    int ans = findN(D);
    Console.WriteLine(ans);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
        // JavaScript code for the above approach 
        function next_prime(x)
        {
            // Edge case
            if (x == 1 || x == 2) {
                return 2;
            }
 
            // Checking if x is prime
            let is_prime = false;
 
            // Loop until next prime is found
            while (!is_prime) {
                is_prime = true;
                for (let i = 2; i <= Math.sqrt(x); i++) {
                    if (x % i == 0) {
                        is_prime = false;
                    }
                }
                x++;
            }
            return x - 1;
        }
 
        // Function to find the number
        function findN(D)
        {
         
            // Assuming 1+D as first required
            // divisor because it is
            // at distance D from 1
            let a = 1 + D;
 
            // Checking whether 1+D is prime or not
            // otherwise it will return prime number
            // just next to it
            a = next_prime(a);
 
            // Checking the same for next divisor
            let b = a + D;
            b = next_prime(b);
 
            let N = a * b;
            return N;
        }
 
        // Driver Code
        let D = 2;
 
        let ans = findN(D);
        document.write(ans);
 
       // This code is contributed by Potta Lokesh
    </script>

Output

Time Complexity: O(N)
Auxiliary Space: 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!