View Discussion
Improve Article
Save Article
ReadDiscussView Discussion
Improve Article
Save Article
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++
#include <bits/stdc++.h>
using namespace std;
int next_prime(int x)
{
if (x == 1 || x == 2) {
return 2;
}
bool is_prime = false;
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;
}
int findN(int D)
{
int a = 1 + D;
a = next_prime(a);
int b = a + D;
b = next_prime(b);
int N = a * b;
return
N;
}
int main()
{
int D = 2;
int ans = findN(D);
cout << ans;
}
Java
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
static int next_prime(int x)
{
if (x == 1 || x == 2) {
return
2;
}
Boolean is_prime = false;
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;
}
static
int findN(int D)
{
int a = 1 + D;
a = next_prime(a);
int b = a + D;
b = next_prime(b);
int N = a * b;
return N;
}
public static void main (String[] args) {
int D = 2;
int ans = findN(D);
System.out.println(ans);
}
}
Python3
def next_prime(x):
if (x == 1 or x == 2):
return 2
is_prime = False
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
def findN(D):
a = 1 + D
a = next_prime(a)
b = a + D
b = next_prime(b)
N = a * b
return N
D =
2
ans = findN(D)
print(ans)
C#
using System;
class GFG {
static int next_prime(int x)
{
if (x == 1 || x == 2) {
return 2;
}
bool is_prime = false;
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;
}
static int findN(int D)
{
int a = 1 + D;
a = next_prime(a);
int b = a + D;
b = next_prime(b);
int N = a * b;
return N;
}
public
static void Main () {
int D = 2;
int ans = findN(D);
Console.WriteLine(ans);
}
}
Javascript
<script>
function next_prime(x)
{
if (x == 1 || x == 2) {
return 2;
}
let is_prime = false;
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 findN(D)
{
let a = 1 + D;
a = next_prime(a);
let b = a + D;
b = next_prime(b);
let N = a * b;
return N;
}
let D = 2;
let ans = findN(D);
document.write(ans);
</script>
Time Complexity:O(N)
Auxiliary Space: O(1)
