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 2Entrada: 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>
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