Devuelve el número primo más cercano

33

Reto

Este es simple: dado un entero positivo de hasta 1,000,000, devuelve el número primo más cercano.

Si el número en sí es primo, entonces debe devolver ese número; Si hay dos primos igualmente cercanos al número proporcionado, devuelva el menor de los dos.

La entrada tiene la forma de un entero entero, y la salida también debe tener la forma de un entero.

No me importa cómo tome la entrada (función, STDIN, etc.) o muestre la salida (función, STDOUT, etc.), siempre que funcione.

Este es el código de golf, por lo que se aplican reglas estándar: ¡gana el programa con la menor cantidad de bytes!

Casos de prueba

Input  =>  Output
------    -------
80     =>      79
100    =>     101
5      =>       5
9      =>       7
532    =>     523
1      =>       2
Nathan Dimmer
fuente
55
Hola y bienvenidos a PPCG! Para evitar la votación negativa debido a la falta de calidad, le sugiero que lo publique primero en la caja de arena y después de un par de días publíquelo aquí
Luis felipe De jesus Munoz
Este es uno de los resultados solicitados en este desafío .
Arnauld
Muy estrechamente relacionado pero no del todo idéntico.
Giuseppe
@Arnauld Vi eso, pero pensé que eran lo suficientemente diferentes como para justificar una nueva pregunta.
Nathan Dimmer
2
Ver también OEIS A051697 .
Eric Towers

Respuestas:

9

Gaia , 3 bytes

ṅD⌡

Pruébalo en línea!

Más bien lento para entradas grandes, pero funciona con suficiente memoria / tiempo.

No estoy seguro de por qué D⌡implícitamente empuja de znuevo, ¡pero hace que esta sea una respuesta notablemente corta!

ṅ	| implicit input z: push first z prime numbers, call it P
 D⌡	| take the absolute difference between P and (implicit) z,
	| returning the smallest value in P with the minimum absolute difference
Giuseppe
fuente
13

JavaScript (ES6), 53 bytes

n=>(g=(o,d=N=n+o)=>N%--d?g(o,d):d-1?g(o<0?-o:~o):N)``

Pruébalo en línea!

Comentado

n => (            // n = input
  g = (           // g = recursive function taking:
    o,            //   o = offset
    d =           //   d = current divisor, initialized to N
    N = n + o     //   N = input + offset
  ) =>            //
    N % --d ?     // decrement d; if d is not a divisor of N:
      g(o, d)     //   do recursive calls until it is
    :             // else:
      d - 1 ?     //   if d is not equal to 1 (either N is composite or N = 1):
        g(        //     do a recursive call with the next offset:
          o < 0 ? //       if o is negative:
            -o    //         make it positive (e.g. -1 -> +1)
          :       //       else:
            ~o    //         use -(o + 1) (e.g. +1 -> -2)
        )         //     end of recursive call
      :           //   else (N is prime):
        N         //     stop recursion and return N
)``               // initial call to g with o = [''] (zero-ish)
Arnauld
fuente
10

05AB1E , 5 bytes

Åps.x

Pruébalo en línea! o como un conjunto de pruebas

Ineficiente para grandes números

Emigna
fuente
3
Lástima Ånque " en caso de empate, se impulsa la prima más alta ". Ni siquiera sabía que teníamos esto incorporado, tbh.
Kevin Cruijssen
@KevinCruijssen: Yo tampoco hasta ahora :)
Emigna
7

Octava , 40 bytes

@(n)p([~,k]=min(abs(n-(p=primes(2*n)))))

Pruébalo en línea!

Esto utiliza el hecho de que siempre hay un primo entre ny 2*n( teorema de Bertrand-Chebyshev ).

Cómo funciona

@(n)p([~,k]=min(abs(n-(p=primes(2*n)))))

@(n)                                      % Define anonymous function with input n
                       p=primes(2*n)      % Vector of primes up to 2*n. Assign to p
                abs(n-(             ))    % Absolute difference between n and each prime
      [~,k]=min(                      )   % Index of first minimum (assign to k; not used)
    p(                                 )  % Apply that index to p
Luis Mendo
fuente
6

Japt , 5 bytes

_j}cU

Pruébalo o ejecuta todos los casos de prueba

_j}cU     :Implicit input of integer U
_         :Function taking an integer as an argument
 j        :  Test if integer is prime
  }       :End function
   cU     :Return the first integer in [U,U-1,U+1,U-2,...] that returns true
Lanudo
fuente
5

Wolfram Language (Mathematica) , 31 bytes

Nearest[Prime~Array~78499,#,1]&

Pruébalo en línea!

                              & (*pure function*)
        Prime~Array~78499       (*among the (ascending) first 78499 primes*)
                            1   (*select one*)
Nearest[                 ,#, ]  (*which is nearest to the argument*)

1000003 es el primo 78499. Nearestprioriza los valores que aparecen antes en la lista (que son más bajos).

attinat
fuente
55
Nearest[Prime@Range@#,#,1]&para 27
Ben
5

Brachylog , 7 5 bytes

;I≜-ṗ

Pruébalo en línea!

Guardado 2 bytes gracias a @DLosc.

Explicación

;I≜      Label an unknown integer I (tries 0, then 1, then -1, then 2, etc.)
   -     Subtract I from the input
    ṗ    The result must be prime
Fatalizar
fuente
@DLosc Principalmente porque soy estúpido. Gracias.
Fatalize
Creo que lo abordamos desde diferentes direcciones. Supongo que estabas pensando desde el principio, mientras que estaba pensando en emparejar y restar y solo más tarde me di cuenta de que tenía que hacerlo funcionar. :)
DLosc
4

Pyth, 10 bytes

haDQfP_TSy

Pruébelo en línea aquí , o verifique todos los casos de prueba a la vez aquí .

haDQfP_TSyQ   Implicit: Q=eval(input())
              Trailing Q inferred
         yQ   2 * Q
        S     Range from 1 to the above
    f         Filter keep the elements of the above, as T, where:
     P_T        Is T prime?
  D           Order the above by...
 a Q          ... absolute difference between each element and Q
                This is a stable sort, so smaller primes will be sorted before larger ones if difference is the same
h             Take the first element of the above, implicit print
Sok
fuente
4

Jalea , 9 7 bytes

ḤÆRạÞµḢ

Pruébalo en línea!

Lento para entradas más grandes, pero funciona bien para el rango solicitado. ¡Gracias a @EriktheOutgolfer por guardar 2 bytes!

Nick Kennedy
fuente
Oye, eso es inteligente! Ahorre dos sustituyendo _A¥con (diferencia absoluta). Ah, y realmente puede ser .
Erik el Outgolfer
@ EriktheOutgolfer gracias. ¿Seguramente usar no siempre funcionará? Significa que solo se encontrarán primos hasta n + 1, mientras que el más cercano podría ser n + 2.
Nick Kennedy el
Hm, eso es una preocupación.
Erik el Outgolfer
4

Python 2 , 71 bytes

f=lambda n,k=1,p=1:k<n*3and min(k+n-p%k*2*n,f(n,k+1,p*k*k)-n,key=abs)+n

Pruébalo en línea!

p(k-1)!2p%kabs(k-n)kk-nabsnk .

La expresión k+n-p%k*2*nestá diseñada para dar k-nprimos (donde p%k=1) y, de lo contrario, un valor "malo" k+nsiempre es mayor en valor absoluto y, por lo tanto, no afecta al mínimo, de modo que se pasan por alto los no primos.

xnor
fuente
3

Ordenado , 43 bytes

{x:(prime↦splice(]x,-1,-∞],[x,∞]))@0}

Pruébalo en línea!

Explicación

Esta es una lambda con parámetro x. Esto funciona creando la siguiente secuencia:

[x - 1, x, x - 2, x + 1, x - 3, x + 2, x - 4, x + 3, ...]

Esto es unir las dos secuencias ]x, -1, -∞](izquierda cerrada, derecha abierta) y[x, ∞] (ambas abiertas).

Para x = 80, esto se ve así:

[79, 80, 78, 81, 77, 82, 76, 83, 75, 84, 74, 85, ...]

Luego, usamos f↦spara seleccionar todos los elementos de ssatisfacción f. En este caso, filtramos todos los números compuestos, dejando solo los primos. Por lo mismo x, esto se convierte en:

[79, 83, 73, 71, 89, 67, 97, 61, 59, 101, 103, 53, ...]

Luego, usamos (...)@0para seleccionar el primer miembro de esta secuencia. Como se debe seleccionar el más bajo de los dos, la secuencia que comienza x - 1se empalma primero.

Nota: Solo uno de xy x - 1puede ser primo, por lo que está bien que comience la secuencia empalmada x - 1. Aunque la secuencia podría estar abierta en ambos lados ( [x,-1,-∞]), esto innecesariamente incluiría xdos veces en la secuencia. Entonces, en aras de la "eficiencia", elegí la versión cerrada a la izquierda (también porque me gusta presumir de Tidy).

Conor O'Brien
fuente
3

APL (Dyalog Extended) , 20 15 bytes SBCS

Función de prefijo tácito inspirada en la respuesta J de Galen Ivanov .

⊢(⊃⍋⍤|⍤-⊇⊢)¯2⍭⍳

Pruébalo en línea!

Encuentra uno a través del argumento.

¯2⍭ enésimos primos de eso

⊢() Aplica la siguiente función tácita a eso, con el argumento original como argumento izquierdo:

 los primos

 indexado por:

   el grado ascendente (índices que ordenarían ascendente)
   de
  | la magnitud (valor absoluto)
   de
  - las diferencias

 elija el primero (es decir, el que tenga la menor diferencia)

Adán
fuente
3

Perl 6 , 35 bytes

{$_+=($*=-1)*$++until .is-prime;$_}

Pruébalo en línea!

Esto utiliza la técnica de Veitcel para generar la lista, 0, -1, 2, -3pero la simplifica enormemente al ($*=-1)*$++usar las variables de estado anónimas disponibles en P6 (originalmente lo tenía -1 ** $++ * $++, pero cuando se juega al golf, el negativo pierde prioridad). Hay un verificador integrado, pero desafortunadamente untilevita el valor devuelto automáticamente, por lo que hay un $_exceso de tiempo.

usuario0721090601
fuente
Por lo general, usaría un enfoque de operador de secuencia para algo como esto, pero sale un byte más , así que es un buen trabajo encontrar un método más corto
Jo King,
@JoKing buena captura. Las cosas que suceden cuando juego golf demasiado rápido después de obtener una solución de trabajo Tuve uno similar pero la maldita falta de [-1] jaja
user0721090601
3

C, 122 121 104 bytes

p(a,i){for(i=1;++i<a;)if(a%i<1)return 0;return a>1;}c(a,b){for(b=a;;b++)if(p(--a)|p(b))return p(b)?b:a;}

Úselo llamando a la función c()y pasando como argumento el número; debería devolver el primo más cercano.

Gracias a Encarnación de la ignorancia por 1 byte ahorró una gran mejora.

Pruébalo en línea!

Lince Assassino
fuente
Pero c()recibe dos parámetros ... Además, probablemente pueda acortar el while(1)a for(;;)(sin probar, ya que no entiendo cómo ejecutar su código
Encarnación de la ignorancia
@EmbodimentofIgnorance Lo escribí y probé todo en un compilador en línea de c , podría llamar c()pasar solo el primer parámetro. Y tienes razón, for(;;)me ahorra un byte, solo quedan 117 para obtener el primer lugar :)
Lince Assassino
110 bytes: #define r return p(a,i){i=1;while(++i<a)if(a%i<1)r 0;r a>1;}c(a,b){b=a;for(;;b++){if(p(--a))r a;if(p(b))r b;}}. Aquí hay un enlace TIO: tio.run/…
Encarnación de la ignorancia
106: tio.run/…
Encarnación de la ignorancia
101: tio.run/…
Encarnación de la ignorancia
2

APL (NARS), 38 caracteres, 76 bytes

{⍵≤1:2⋄0π⍵:⍵⋄d←1π⍵⋄(d-⍵)≥⍵-s←¯1π⍵:s⋄d}

0π es la prueba de primo, ¯1π el primo anterior, 1π es el próximo primo; prueba:

  f←{⍵≤1:2⋄0π⍵:⍵⋄d←1π⍵⋄(d-⍵)≥⍵-s←¯1π⍵:s⋄d}
  f¨80 100 5 9 532 1
79 101 5 7 523 2 
RosLuP
fuente
2

Perl 5 , 59 bytes

$a=0;while((1x$_)=~/^.?$|^(..+?)\1+$/){$_+=(-1)**$a*($a++)}

Pruébalo en línea!

/^.?$|^(..+?)\1+$/ es complicado regexp para comprobar prime

(-1)**$a*($a++) generar secuencia 0, -1, 2, -3 ...

Veitcel
fuente
2

MathGolf , 10 bytes

∞╒g¶áÅ-±├Þ

Pruébalo en línea.

Explicación:

            # Double the (implicit) input-integer
            # Create a list in the range [1, 2*n]
  g         # Filter so only the prime numbers remain
    áÅ       # Sort this list using the next two character:
           #  The absolute difference with the (implicit) input-integer
            # Push the first item of the list
             # (unfortunately without popping the list itself, so:)
         Þ   # Discard everything from the stack except for the top
             # (which is output implicitly as result)
Kevin Cruijssen
fuente
@JoKing ¡Gracias! Sabía que Max pensaba en cambiarlo, pero no sabía que realmente lo hacía. Los documentos todavía indican el antiguo.
Kevin Cruijssen
Ah, uso el archivo mathgolf.txt como referencia, ya que parece estar más actualizado
Jo King
@JoKing Sí, ayer también me contó sobre ese archivo. Lo usará de ahora en adelante. :)
Kevin Cruijssen
2

Python 2 (Cython) , 96 bytes

l=lambda p:min(filter(lambda p:all(p%n for n in range(2,p)),range(2,p*3)),key=lambda x:abs(x-p))

Pruébalo en línea!

Dispensador Snaddyvitch
fuente
Podría guardar un par de bytes a través der=range;...
Skyler
1
@Arnauld, ahora funciona para x = 1
Snaddyvitch Dispenser
2

C # (compilador interactivo de Visual C #) , 104 100 bytes

n=>{int r=0,t=0,m=n;while(r!=2){n+=(n<m)?t:-t;t++;r=0;for(int i=1;i<=n;i++)if(n%i==0)r++;}return n;}

Pruébalo en línea!

Explicación:

int f(int n)
{
    int r = 0; //stores the amount of factors of "n"
    int t = 0; //increment used to cover all the integers surrounding "n"
    int m = n; //placeholder to toggle between adding or substracting "t" to "n"

    while (r != 2) //while the amount of factors found for "n" is different to 2 ("1" + itself)
    {
        n += (n < m) ? t : -t; //increment/decrement "n" by "t" (-0, -1, +2, -3, +4, -5,...)
        t++;
        r = 0;
        for (int i = 1; i <= n; i++) //foreach number between "1" and "n" increment "r" if the remainder of its division with "n" is 0 (thus being a factor)
            if (n % i == 0) r++; 
    }
    return n;
}

Console.WriteLine(f(80)); //79
Innat3
fuente
2

Java 8, 88 87 bytes

n->{for(int c=0,s=0,d,N=n;c!=2;s++)for(c=d=1,n+=n<N?s:-s;d<n;)if(n%++d<1)c++;return n;}

Puerto de la respuesta C de @NaturalNumberGuy (primera) , ¡ así que asegúrate de votarlo!
-1 byte gracias a @ OlivierGrégoire .

Pruébalo en línea.

Explicación:

n->{               // Method with integer as both parameter and return-type
  for(int c=0,     //  Counter-integer, starting at 0
          s=0,     //  Step-integer, starting at 0 as well
          d,       //  Divisor-integer, uninitialized
          N=n;     //  Copy of the input-integer
      c!=2;        //  Loop as long as the counter is not exactly 2 yet:
      s++)         //    After every iteration: increase the step-integer by 1
    for(c=d=1,     //   (Re)set both the counter and divisor to 1
        n+=n<N?    //   If the input is smaller than the input-copy:
            s      //    Increase the input by the step-integer
           :       //   Else:
            -s;    //    Decrease the input by the step-integer
        d<n;)      //   Inner loop as long as the divisor is smaller than the input
      if(n%++d     //    Increase the divisor by 1 first with `++d`
              <1)  //    And if the input is evenly divisible by the divisor:
        c++;       //     Increase the counter-integer by 1
  return n;}       //  Return the now modified input-integer as result
Kevin Cruijssen
fuente
2

Java (JDK) , 103 bytes

n->{int p=0,x=0,z=n,d;for(;p<1;p=p>0?z:0,z=z==n+x?n-++x:z+1)for(p=z/2,d=1;++d<z;)p=z%d<1?0:p;return p;}

Pruébalo en línea!

Olivier Grégoire
fuente
Umm ... ya había creado un puerto de su respuesta ... ;) Aunque la tuya es 1 byte más corta, entonces algo es diferente. EDITAR: Ah, tengo un número entero de resultados fuera del bucle, y usted modifica la entrada dentro del bucle, de ahí el byte -1 para ;. :) ¿Quieres que elimine mi respuesta? .. No dudes en copiar la explicación.
Kevin Cruijssen
@KevinCruijssen ¡Vaya, retrocedió!
Olivier Grégoire
Lo siento por eso (y gracias por el byte -1). Sin embargo, también me gusta tu versión. Ya voté antes de ver la respuesta de NaturalNumberGuy.
Kevin Cruijssen
2

Haskell , 79 74 bytes (gracias a Laikoni)

72 bytes como función annonymus (la "f =" inicial podría eliminarse en este caso).

f=(!)(-1);n!x|x>1,all((>0).mod x)[2..x-1]=x|y<-x+n=last(-n+1:[-n-1|n>0])!y

Pruébalo en línea!


código original:

f=(!)(-1);n!x|x>1&&all((>0).mod x)[2..x-1]=x|1>0=(last$(-n+1):[-n-1|n>0])!(x+n)

Pruébalo en línea!

Explicación:

f x = (-1)!x

isPrime x = x > 1 && all (\k -> x `mod` k /= 0)[2..x-1]
n!x | isPrime x = x            -- return the first prime found
    | n>0       = (-n-1)!(x+n) -- x is no prime, continue with x+n where n takes the 
    | otherwise = (-n+1)!(x+n) -- values -1,2,-3,4 .. in subsequent calls of (!)
Sachera
fuente
1
Dentro de un guardia puedes usar en ,lugar de &&. (last$ ...)puede ser last(...), y la segunda protección 1>0se puede utilizar para un enlace para guardar paréntesis, por ejemplo y<-x+n.
Laikoni
Las funciones anónimas generalmente están permitidas, por lo que f=no es necesario contar la inicial . También (-1+n)se puede descartar el paréntesis .
Laikoni
Gracias por las sugerencias ¡No sabía "," y los enlaces están permitidos en los guardias de funciones! Pero realmente no me gusta la idea de una función anónima como respuesta. No se siente bien en mi opinión.
Sachera
Puede encontrar más consejos en nuestra colección de consejos para jugar al golf en Haskell . También hay una Guía de reglas de golf en Haskell y una sala de chat dedicada: De mónadas y hombres .
Laikoni
2

VDM-SL , 161 bytes

f(i)==(lambda p:set of nat1&let z in set p be st forall m in set p&abs(m-i)>=abs(z-i)in z)({x|x in set{1,...,9**7}&forall y in set{2,...,1003}&y<>x=>x mod y<>0})

Un programa completo para ejecutar podría tener este aspecto: vale la pena señalar que los límites del conjunto de primos utilizados probablemente deberían cambiarse si realmente desea ejecutar esto, ya que tomará mucho tiempo ejecutarlo por 1 millón:

functions
f:nat1+>nat1
f(i)==(lambda p:set of nat1&let z in set p be st forall m in set p&abs(m-i)>=abs(z-i)in z)({x|x in set{1,...,9**7}&forall y in set{2,...,1003}&y<>x=>x mod y<>0})

Explicación:

f(i)==                                        /* f is a function which takes a nat1 (natural number not including 0)*/
(lambda p:set of nat1                         /* define a lambda which takes a set of nat1*/
&let z in set p be st                         /* which has an element z in the set such that */
forall m in set p                             /* for every element in the set*/
&abs(m-i)                                     /* the difference between the element m and the input*/
>=abs(z-i)                                    /* is greater than or equal to the difference between the element z and the input */
in z)                                         /* and return z from the lambda */
(                                             /* apply this lambda to... */
{                                             /* a set defined by comprehension as.. */
x|                                            /* all elements x such that.. */ 
x in set{1,...,9**7}                          /* x is between 1 and 9^7 */
&forall y in set{2,...,1003}                  /* and for all values between 2 and 1003*/
&y<>x=>x mod y<>0                             /* y is not x implies x is not divisible by y*/
} 
)
Datos caducados
fuente