Dado un entero positivo N , la tarea es encontrar la diferencia absoluta de N y el número primo más cercano a N .
Nota: El número primo más cercano a N puede ser menor, igual o mayor que N.
Ejemplos:
Entrada: N = 25
Salida: 2
Para N = 25
El primo más cercano mayor que 25 es 29. Por lo tanto, la diferencia es 4.
El primo más cercano menor que 25 es 23. Por lo tanto, la diferencia es 2.
El mínimo de estos dos es 2.
Entrada: N = 2
Salida: 0
Como 2 en sí mismo es un número primo, el número primo más cercano es 2. Entonces, la diferencia es 0.
Acercarse:
- Si N es primo , imprima 0 .
- De lo contrario, encuentra el primer número primo > N y observa su diferencia con N .
- Luego, encuentre el primer número primo < N y observe su diferencia con N .
- E imprimir el mínimo de estas dos diferencias obtenidas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the minimum absolute
// difference between a number and its closest prime
#include <bits/stdc++.h>
using namespace std;
// Function to check if a number is prime or not
bool isPrime(int N)
{
for (int i = 2; i <= sqrt(N); i++) {
if (N % i == 0)
return false;
}
return true;
}
// Function to find the minimum absolute difference
// between a number and its closest prime
int getDifference(int N)
{
if (N == 0)
return 2;
else if (N == 1)
return 1;
else if (isPrime(N))
return 0;
// Variables to store first prime
// above and below N
int aboveN = -1, belowN = -1;
int n1;
// Finding first prime number greater than N
n1 = N + 1;
while (true) {
if (isPrime(n1)) {
aboveN = n1;
break;
}
else
n1++;
}
// Finding first prime number less than N
n1 = N - 1;
while (true) {
if (isPrime(n1)) {
belowN = n1;
break;
}
else
n1--;
}
// Variables to store the differences
int diff1 = aboveN - N;
int diff2 = N - belowN;
return min(diff1, diff2);
}
// Driver code
int main()
{
int N = 25;
cout << getDifference(N) << endl;
return 0;
// This code is contributed by Ryuga
}
Java
// Java program to find the minimum absolute
// difference between a number and its closest prime
class GFG {
// Function to check if a number is prime or not
static boolean isPrime(int N)
{
for (int i = 2; i <= Math.sqrt(N); i++) {
if (N % i == 0)
return false;
}
return true;
}
// Function to find the minimum absolute difference
// between a number and its closest prime
static int getDifference(int N)
{
if (N == 0)
return 2;
else if (N == 1)
return 1;
else if (isPrime(N))
return 0;
// Variables to store first prime
// above and below N
int aboveN = -1, belowN = -1;
int n1;
// Finding first prime number greater than N
n1 = N + 1;
while (true) {
if (isPrime(n1)) {
aboveN = n1;
break;
}
else
n1++;
}
// Finding first prime number less than N
n1 = N - 1;
while (true) {
if (isPrime(n1)) {
belowN = n1;
break;
}
else
n1--;
}
// Variables to store the differences
int diff1 = aboveN - N;
int diff2 = N - belowN;
return Math.min(diff1, diff2);
}
// Driver code
public static void main(String args[])
{
int N = 25;
System.out.println(getDifference(N));
}
}
Python3
# Python 3 program to find the minimum # absolute difference between a number # and its closest prime from math import sqrt # Function to check if a number is # prime or not def isPrime(N): k = int(sqrt(N)) + 1 for i in range(2, k, 1): if (N % i == 0): return False return True # Function to find the minimum absolute # difference between a number and its # closest prime def getDifference(N): if (N == 0): return 2 elif (N == 1): return 1 elif (isPrime(N)): return 0 # Variables to store first prime # above and below N aboveN = -1 belowN = -1 # Finding first prime number # greater than N n1 = N + 1 while (True): if (isPrime(n1)): aboveN = n1 break else: n1 += 1 # Finding first prime number # less than N n1 = N - 1 while (True): if (isPrime(n1)): belowN = n1 break else: n1 -= 1 # Variables to store the differences diff1 = aboveN - N diff2 = N - belowN return min(diff1, diff2) # Driver code if __name__ == '__main__': N = 25 print(getDifference(N)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find the minimum absolute
// difference between a number and its closest prime
using System;
class GFG {
// Function to check if a number is prime or not
static bool isPrime(int N)
{
for (int i = 2; i <= Math.Sqrt(N); i++) {
if (N % i == 0)
return false;
}
return true;
}
// Function to find the minimum absolute difference
// between a number and its closest prime
static int getDifference(int N)
{
if (N == 0)
return 2;
else if (N == 1)
return 1;
else if (isPrime(N))
return 0;
// Variables to store first prime
// above and below N
int aboveN = -1, belowN = -1;
int n1;
// Finding first prime number greater than N
n1 = N + 1;
while (true) {
if (isPrime(n1)) {
aboveN = n1;
break;
}
else
n1++;
}
// Finding first prime number less than N
n1 = N - 1;
while (true) {
if (isPrime(n1)) {
belowN = n1;
break;
}
else
n1--;
}
// Variables to store the differences
int diff1 = aboveN - N;
int diff2 = N - belowN;
return Math.Min(diff1, diff2);
}
// Driver code
public static void Main()
{
int N = 25;
Console.WriteLine(getDifference(N));
}
}
// This code is contributed by anuj_67..
PHP
<?php
// PHP program to find the minimum absolute
// difference between a number and its
// closest prime
// Function to check if a number
// is prime or not
function isPrime($N)
{
for ($i = 2; $i <= sqrt($N); $i++)
{
if ($N % $i == 0)
return false;
}
return true;
}
// Function to find the minimum absolute difference
// between a number and its closest prime
function getDifference($N)
{
if ($N == 0)
return 2;
else if ($N == 1)
return 1;
else if (isPrime($N))
return 0;
// Variables to store first prime
// above and below N
$aboveN = -1; $belowN = -1;
// Finding first prime number greater than N
$n1 = $N + 1;
while (true)
{
if (isPrime($n1))
{
$aboveN = $n1;
break;
}
else
$n1++;
}
// Finding first prime number less than N
$n1 = $N - 1;
while (true)
{
if (isPrime($n1))
{
$belowN = $n1;
break;
}
else
$n1--;
}
// Variables to store the differences
$diff1 = $aboveN - $N;
$diff2 = $N - $belowN;
return min($diff1, $diff2);
}
// Driver code
$N = 25;
echo getDifference($N) . "\n";
// This code is contributed
// by Akanksha Rai
Javascript
// Javascript program to find the minimum absolute
// difference between a number and its
// closest prime
// Function to check if a number
// is prime or not
function isPrime(N)
{
for (let i = 2; i <= Math.sqrt(N); i++)
{
if (N % i == 0)
return false;
}
return true;
}
// Function to find the minimum absolute difference
// between a number and its closest prime
function getDifference(N)
{
if (N == 0)
return 2;
else if (N == 1)
return 1;
else if (isPrime(N))
return 0;
// Variables to store first prime
// above and below N
let aboveN = -1;
let belowN = -1;
// Finding first prime number greater than N
let n1 = N + 1;
while (true)
{
if (isPrime(n1))
{
aboveN = n1;
break;
}
else
n1++;
}
// Finding first prime number less than N
n1 = N - 1;
while (true)
{
if (isPrime(n1))
{
belowN = n1;
break;
}
else
n1--;
}
// Variables to store the differences
let diff1 = aboveN - N;
let diff2 = N - belowN;
return Math.min(diff1, diff2);
}
// Driver code
let N = 25;
document.write(getDifference(N) + "<br>");
// This code is contributed
// by gfgking
Producción:
2
Complejidad de tiempo: O(N*sqrt(N)), donde N representa el entero dado.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Publicación traducida automáticamente
Artículo escrito por rachana soma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA