4 divisors code in python

View Discussion

Improve Article

Save Article

View 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

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

Time Complexity:O(N)
Auxiliary Space: O(1)