Número más pequeño que tiene solo 4 divisores con diferencia entre dos cualesquiera como máximo D

Dado el número D , encuentra el número N más pequeño tal que tenga exactamente cuatro divisores y la diferencia entre dos cualesquiera de ellos sea mayor o igual que D.

Ejemplos:

Entrada: 1
Salida: 6
Explicación: 6 tiene cuatro divisores 1, 2, 3 y 6. 
La diferencia entre dos de ellos siempre es mayor o igual a 1.

Entrada: 2
Salida: 15
Explicación: 15 tiene cuatro divisores 1, 3, 5 y 15. 
La diferencia entre dos de ellos siempre es mayor o igual a 2

Entrada: 3
Salida: 55
Explicación: 55 tiene cuatro divisores 1, 5, 11 y 55. 
La diferencia entre dos de ellos siempre es mayor que 3.

 

Enfoque: Es obvio que ‘1’ y el número mismo son los divisores de N . Entonces, el número que tiene exactamente 4 divisores tiene sus divisores como 1, a, b, a*b respectivamente. Para la condición de que tenga exactamente 4 divisores, tanto a como b deben ser primos . Para la condición de que la diferencia entre dos cualquiera de ellos sea al menos D , comience a encontrar a de 1+d y verifique si es primo o no. Si no es primo, encontraremos el número primo justo al lado. Del mismo modo, comience a encontrar b de a + dy verifique si es primo o no, y haga lo mismo que para encontrar un .

A continuación se muestra la implementación del enfoque anterior.

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>
Producción

15

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por jainuditkumar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *