Smallest number having only 4 divisors with difference between any two at most D
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 2Input: 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 numberint 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 Codeint main(){ int D = 2; int ans = findN(D); cout << ans;} |
Java
// Java program for the above approachimport 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 approachdef 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 numberdef 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 CodeD = 2ans = findN(D)print(ans)# This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approachusing 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> |
15
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
