Factor primo o más alto

14

Desafío:

Dada una matriz de números enteros no negativos en el rango de0 to Infinity , Verifique si todos son números primos o no. (También puede tomar la entrada como una cadena si lo desea)

Entrada:

Entrada: una matriz de números

Salida: la matriz con cada elemento reemplazado por uno de estos:

-1                 -----> If 0, 1
1                  -----> If it is a prime number greater than 1
the highest factor -----> If that number is not prime

Devuelve -1 (0, 1), 1 (para números primos> = 2) o el factor más alto del número dado (para números no primos)

Ejemplos:

[1, 2, 3, 4, 10, 11, 13]                        ---> [-1, 1, 1, 2, 5, 1, 1]
[100, 200, 231321, 12312, 0, 111381209, 123123] ---> [50, 100, 77107, 6156, -1, 1, 41041]

Nota:

La entrada siempre será válida, es decir, consistirá solo en números y no se probarán los decimales. La matriz puede estar vacía, de ser así, devuelva la matriz vacía.

Restricción:

Este es el por lo que gana el código más corto en bytes para cada idioma.

LeaderBoard:

Aquí hay un fragmento de pila para generar una tabla de clasificación regular y una descripción general de los ganadores por idioma.

Para asegurarse de que su respuesta se muestre, comience con un título, usando la siguiente plantilla de Markdown:

# Language Name, N bytes

¿Dónde Nestá el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Si desea incluir varios números en su encabezado (por ejemplo, porque su puntaje es la suma de dos archivos o desea enumerar las penalizaciones de la bandera del intérprete por separado), asegúrese de que el puntaje real sea el último número en el encabezado:

# Perl, 43 + 2 (-p flag) = 45 bytes

También puede hacer que el nombre del idioma sea un enlace que luego aparecerá en el fragmento de la tabla de clasificación:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes


fuente
2
Recomiendo usar el Sandbox para futuras preguntas, para proporcionar comentarios sobre las preguntas antes de publicarlas
Jo King,
@ Bromas: para el infinito, debe generar todos los números hasta el infinito. Esto es solo para usted y también debe asegurarse de que no se agote el tiempo ni nada. JK: el error de tiempo de espera es lo más probable que obtendrá para el infinito
44
solo quería señalar que en "Si es un número primo mayor que 1" mayor que 1 realmente no es necesario porque los números primos siempre son mayores que 1
Ivo Beckers
55
Definir el factor más alto. ¿Debo devolver el número en sí? ¿El primo divisible más alto? ¿El factor más alto que no es en sí mismo?
Nissa
2
Supongo que nuestros programas solo están obligados a trabajar con números enteros hasta el tamaño máximo de número entero de nuestro idioma elegido (para aquellos que no tienen soporte para números enteros arbitrariamente grandes)
JDL

Respuestas:

9

Gelatina ,  7 6 bytes

ÆḌṪ€o-

Un enlace monádico que acepta una lista de enteros no negativos y retiene una lista de enteros mayores o iguales a -1.

Pruébalo en línea!

¿Cómo?

Tenga en cuenta que:

  • Todos los números primos tienen un solo divisor propio (uno)
  • Todos los compuestos tienen múltiples divisores propios (uno más los otros)
  • Ningún número se tiene como divisor propio
  • El átomo de los divisores propios de Jelly ÆḌproduce una lista de divisores propios en orden ascendente
  • Cero y uno no tienen divisores propios (no son primos ni compuestos)
  • Aplicando el átomo de la cola de Jelly , a una lista vacía, se obtiene cero
  • Ningún número tiene un divisor propio de cero (y mucho menos ser el máximo)
  • Todos los números distintos de cero son verdaderos en Jelly, mientras que cero es falsey

ÆḌṪ€o- | Link: list of integers   e.g. [ 0, 1,  2,  5,     10,    5183]
ÆḌ     | proper divisors (vectorises)  [[],[],[1],[1],[1,2,5],[1,71,73]]
  Ṫ€   | tail €ach                     [ 0, 0,  1,  1,      5,      73]
     - | literal minus one
    o  | logical OR (vectorises)       [-1,-1,  1,  1,      5,      73]
Jonathan Allan
fuente
8

Jalea , 9 8 bytes

Guardado 1 byte gracias a @Dennis

:ÆfṂ€$~~

Pruébalo en línea! o ejecutar todos los casos de prueba

Comentado

Aprovechamos el hecho de que ambos nany nos infconvertimos 0en Jelly cuando NO se les aplica un bit a bit.

:ÆfṂ€$~~ - main link, taking the input list
 ÆfṂ€$   - treat these two links as a monad:
 Æf      -   get the lists of prime factors (0 --> 0; 1 --> empty list; prime --> itself)
    €    -   for each list,
   Ṃ     -   isolate the minimum prime factor (turns empty lists into 0)
:        - divide each entry by its minimum prime factor (0/0 --> nan; 1/0 --> inf)
      ~~ - bitwise NOT x2 (nan or inf --> 0 --> -1; other entries are unchanged)
Arnauld
fuente
3
¿No usaste JavaScript esta vez? buena respuesta por cierto
3
Realmente me gusta el ~~. :ÆfṂ€$~~guarda un byte al eliminar el enlace auxiliar.
Dennis
@Dennis Ah! $es lo que estaba buscando :) ¡Gracias!
Arnauld
7

R, 68 62 bytes

Map(function(n,v=rev(which(!n%%1:n)))"if"(n<2,-1,v[2]),scan())

¡Una solución que usa solo base R, sin bibliotecas! Gracias a Giuseppe por jugar al golf 6 bytes.

Utiliza scanpara leer en una lista de números separados por espacios, %%para identificar cuáles son los factores. vluego contiene un vector de todos los factores en orden ascendente (incluidos 1 yn). Esto tiene la buena propiedad de que cuando revescribimos v, el número que queremos estará en segundo lugar, evitando una llamada costosa lengtho tail(si nera primo, vcontiene n 1, de lo contrario contiene n (factors in descending order) 1).

Ejemplo de salida (enlace TIO aquí ):

> Map(function(n,v=rev(which(!n%%1:n)))"if"(n<2,-1,v[2]),scan())
1: 0 1 2 3 4 5 6 7 8 9
11: 
Read 10 items
[[1]]
[1] -1

[[2]]
[1] -1

[[3]]
[1] 1

[[4]]
[1] 1

[[5]]
[1] 2

[[6]]
[1] 1

[[7]]
[1] 3

[[8]]
[1] 1

[[9]]
[1] 4

[[10]]
[1] 3

Si cree que una lista no es un tipo de retorno aceptable, entonces intercambiar Mappor sapplyy añadir 3 bytes.

JDL
fuente
2
62 bytes
Giuseppe
agradable - no pensé inicializar con!
JDL
6

05AB1E , 11 9 8 bytes

Ñε¨àDd<+

-3 bytes gracias a @Emigna , cambiando ©d1-®+a Dd<+y €¨€àpara ε¨à.

Solo mi segunda respuesta 05AB1E, por lo que definitivamente se puede jugar al golf .

Pruébalo en línea.

Explicación:

Ñ           # Divisors of each item in the input-list (including itself)
            #  [1,2,10,3] → [[1],[1,2],[1,2,5,10],[1,2,3]]
 ε          # For each:
  ¨         #  Remove last item (so it's now excluding itself)
            #   [[1],[1,2],[1,2,5,10],[1,2,3]] → [[],[1],[1,2,5],[1,2]]
   à        #  And get the max
            #   [[],[1],[1,2,5],[1,2]] → ['',1,5,2]
    D       # Duplicate the list
     d      # Is it a number (1 if it's a number, 0 otherwise)
            #  ['',1,5,2] → [0,1,1,1]
      <     # Subtract 1
            #  [0,1,1,1] → [-1,0,0,0]
       +    # Add both lists together
            #  ['',1,5,2] and [-1,0,0,0] → ['-1',1,5,2]
Kevin Cruijssen
fuente
1
Dd<+debería funcionar en lugar de ©d1-®+. Tampoco necesitas el ïya que todavía son ints. Sin embargo, podría tenerlo en el pie de página para una salida más bonita.
Emigna
@Emigna Ah, en 1-lugar de <fue bastante estúpido ... ¡Gracias por el en Dlugar de ©...®! Y de hecho he puesto ïel pie de página ahora.
Kevin Cruijssen
1
O incluso mejor:Ñε¨àDd<+
Emigna
Mucho mejor que mi 12 byter.
Urna de pulpo mágico
5

J , 21 bytes

_1:`(%{.@q:)@.(>&1)"0

Pruébalo en línea!

Explicación:

(>&1)"0 ¿Es cada número mayor que 1?

@. si no, regrese _1:

(%{.@q:)si es 2 o mayor, divida %el número por el primero {.de los factores primosq:

Galen Ivanov
fuente
4

Japt , 6 bytes

Después de jugar al golf, terminó siendo casi idéntico y tan corto como la solución de Jonathan.

®â¬ÌªJ

Intentalo


Explicación

®          :Map
 ⬠       :  Proper divisors
   Ì       :  Get last element (returns null if the array is empty)
    ª      :  Logical OR
     J     :  -1
Lanudo
fuente
Guardar un byte con-m
Oliver
3

Python 3 , 62 bytes

lambda l:[max([k for k in range(1,n)if n%k<1]+[-1])for n in l]

Pruébalo en línea!

Para 0y 1 range(1,n)está vacío, por lo tanto, el código se evalúa como max([]+[-1]) = -1. Para los números primos, el único divisor en [1, n) es 1, que es la salida deseada.


Coco , 50 bytes

map$(n->max([k for k in range(1,n)if n%k<1]+[-1]))

Pruébalo en línea!

ovs
fuente
3

Java 8, 105 103 87 bytes

a->{for(int i=a.length,n,x;i-->0;a[i]=n<2?-1:n/x)for(n=a[i],x=1;++x<n;)if(n%x<1)break;}

Modifica la matriz de entrada en lugar de devolver una nueva para guardar bytes.

Pruébalo en línea.

Explicación:

a->{                  // Method with integer-array parameter and no return-type
  for(int i=a.length,n,x;i-->0;
                      //  Loop backward over the array
      a[i]=           //    After every iteration: change the current item to:
           n<2?       //     If the current item is 0 or 1:
            -1        //      Change it to -1
           :          //     Else:
            n/x)      //      Change it to `n` divided by `x`
     for(n=a[i],      //   Set `n` to the current item
         x=1;++x<n;)  //   Inner loop `x` in range [2,`n`)
       if(n%x<1)      //    If `n` is divisible by `x`:
         break;}      //     Stop the inner loop (`x` is now the smallest prime-factor)
                      //   (if the loop finishes without hitting the `break`,
                      //    it means `n` is a prime, and `x` and `n` will be the same)
Kevin Cruijssen
fuente
3

Haskell, 52 49 bytes

map(\x->last$[d|d<-[1..x-1],mod x d<1]++[-1|x<2])

Pruébalo en línea!

map                     -- for each element in the input array
  \x->                  -- apply the lambda function
    last                -- pick the last element of the following list
     [d|d<-[1..x-1]     --  all d from 1 to x-1 
           ,mod x d<1]  --    where d divides x 
     ++[-1|x<2]         --  followed by -1 if x<2
nimi
fuente
3

Casco , 8 bytes

m(|_1→hḊ

Pruébalo en línea!

Explicación

m(|_1→hḊ  Implicit Input         [1,2,3,4,10]
m(        Map each element
       Ḋ    List of divisors     [[1],[1,2],[1,3],[1,2,4],[1,2,5,10]]
     →h     Penultimate element  [0,1,1,2,5]
  |_1       If falsy then -1     [-1,1,1,2,5]
Fyr
fuente
3

Adjunto , 23 bytes

@{Max&-1!Divisors@_@-2}

Pruébalo en línea!

29 bytes, sin puntos: @(Max&-1@Last@ProperDivisors)

24 bytes, también sin puntos: @(Max&-1@`@&-2@Divisors)

Esto simplemente obtiene el penúltimo divisor de, nluego toma el máximo de él y -1. El penúltimo elemento de una matriz con menos de dos elementos es nily Max[-1, nil]es -1. @simplemente vectoriza esta función, haciendo que se aplique a cada átomo.

Conor O'Brien
fuente
2

R + numbers, 88 79 bytes

Gracias a los comentarios por algunos consejos principalmente sobre cómo hacer presentaciones.

function(y)sapply(y,function(x)"if"(x<2,-1,prod(numbers::primeFactors(x)[-1])))

Utiliza el producto de todos los factores primos, excepto el más pequeño, y el hecho de que el producto de los elementos de un vector vacío se define como ser 1.

Pruébalo en línea!

ngm
fuente
1
guarda bytes para omitir la libraryllamada y usar numbers::primeFactorsdirectamente.
JDL
1
Aquí hay un enlace TIO para ver lo que sugiere JDL, así como cambiarlo a una función anónima.
Giuseppe
2

Brachylog , 10 bytes

{fkt|∧_1}ˢ

Pruébalo en línea!

La siguiente explicación se formula principalmente en aras de la brevedad, y no refleja con precisión la naturaleza declarativa de Brachylog.

{          Start of inline predicate.
           Implicit input to the predicate.
 f         Create a list of all of the input's factors (including itself).
  k        Remove the last item of this list so that it no longer contains the original number.
   t       Take the last item of the list with the last item removed.
           Implicitly unify the output with the aforementioned last item.
    |      If that failed, because one of the lists was empty...
     ∧     discarding the input, (there's probably some obvious reason ∨ won't work here but I don't know what it is)
      _1   unify the output with -1 instead.
        }  End of the inline predicate.
         ˢ For every item of the input, unify it with the predicate's input and get a list of the corresponding outputs.

Decidí que aprendería Brachylog para poder divertirme con el golf de código mientras esperaba aprender algo del comportamiento de Prolog real a través de la ósmosis, y realmente lo estoy disfrutando hasta ahora, incluso si no estoy completamente seguro de cómo Los personajes de control de ejecución funcionan.

Cadena no relacionada
fuente
2
"probablemente haya alguna razón obvia ∨ no funcionará aquí, pero no sé qué es" -> Puede usarlo en .∨lugar de |∧(supongo que olvidó el .), pero es el mismo conteo de bytes. Bienvenido a PPCG (y Brachylog más importante: p) por cierto.
Fatalize
Ah, por supuesto! Gracias.
Cadena no relacionada
Puede hacer este tipo de preguntas en Brachylog en la sala de chat de Brachylog
Fatalize
1

Stax , 14 13 bytes

ü±p╞Ö*«òτ♀╣â▀

Ejecutar y depurarlo

Explicación (sin embalaje):

m|fc%c{vsH1?}U? Full program, implicit input-parsing
m               Map
 |fc%c            Get factorisation and length of it (0 and 1 yield [])
      {     } ?   If length != 0:
       v            Decrement
           ?        If still != 0:
        sH            Last element of factorisation
           ?        Else:
          1           Push 1
              ?   Else:
             U      Push -1

Pseudocódigo dentro del mapa:

f = factorisation(i)
l = length(f)
if l:
    if --l:
        return f[-1]
    else:
        return 1
else:
    return -1
wastl
fuente
1

Pyth, 12 bytes

me+_1f!%dTSt

Pruébalo aquí

Explicación

me+_1f!%dTSt
m            Q    For each number d in the (implicit) input...
          Std     ... get the range [1, ..., d - 1]...
     f!%dT        ... take the ones that are factors of d...
  +_1             ... prepend -1...
 e                ... and take the last.

fuente
1

J , 14 bytes

1(%0{q:,-)@>.]

Pruébalo en línea!

Por cada número n tome el máximo de (n, 1) en su lugar.
Agregue el número negado a la lista de sus factores primos (lista vacía para 1) y divida el número por el primer elemento de la lista.

También 14 bytes

(%0{q:) ::_1"0

Pruébalo en línea!

Divide cada número por el primero de sus factores primos. 0 genera un error de dominio con q:, y buscamos el elemento 0 en una lista vacía para 1; eso también es un error. Para cualquier número que tenga errores, devuelve -1.

FrownyFrog
fuente
Muy buenas soluciones!
Galen Ivanov
1

Japt , 14 11 8 bytes

®/k v)ªÉ
®        // For each input number,
 /k v    // return the number divided by it's first prime factor,
     )ªÉ // or -1 if such a number doesn't exist (the previous result is NaN).

Pruébalo en línea!

Afeitó esos tres molestos bytes gracias a Shaggy .

Liendre
fuente
No necesita filtrar los números primos, kdevuelve los factores primos de N, por lo que esto se convierte en 8 bytes:®/k v)ªÉ
Shaggy
@Shaggy Gracias, no sabía que solo devuelve los factores primos, ya que los documentos del método no dicen eso.
Nit
1
Oh, sí, lo olvidé. Ha tenido la intención de enviar un RP por un tiempo; Lo haré en breve.
Shaggy
1

JavaScript (Node.js) , 61 55 bytes

-6 bytes gracias a @shaggy

_=>_.map(_=>eval('for(v=_/(d=_>>1);v!=~~v;v=_/--d);d'))

Pruébalo en línea!


Explicación

_ =>                                     // input i.e : the original array
    _.map(                               // map over all elements of the array
        eval('                           // eval a string
            for(v=_/(d=_>>1);            // set v = _ / _ >> 1 and set that to d
                v!=~~v;                  // and keep going until v !== floor(v)
                        v=_/d--);        // to _ / d again (d was changed)
                    d'                   // return d
            ))                           // end eval and map and function

Esto todavía es para el código antiguo que no ha actualizado esto.

ES5 amigable también:

 const primeOrNot = function(input) { // the function with argument input
      return input.map(function(value) { // returns the array after mapping over them
           d = Math.floor(value * 0.5); // multiply each element by 0.5 and floor it 
           for(let v = value / d; v != Math.floor(v);) { // for loop goes until v!=~~v
                d --; // subtract one from d
                v = value / d; // set v again to value / d
           }
           return d; // return d
      })
 };
Muhammad Salman
fuente
55 bytes
Shaggy
@ Shaggy: gracias
Muhammad Salman
1

Bash + utilidades GNU, 49

  • 9 bytes guardados gracias a @Cowsquack
factor|sed '/:$/c-1
/: \w+$/c1
s%: %/%
y/ /#/'|bc

Explicación

  • factor lee números de entrada de STDIN, uno por línea y salidas en el formato <input number>: <space-separated list of prime factors (ascending)>
  • sed procesa esto de la siguiente manera:
    • /:$/c-1 Los números de entrada 0 y 1 no tienen factores primos y se reemplazan con -1
    • /: \w+$/c1Los números con un factor primo (ellos mismos) son primos. Reemplace estos con1
    • s%: %/%Reemplazar :con/ . Esto crea una expresión aritmética para dividir el número de entrada (no primo) por su factor primo más pequeño para dar el factor más grande
    • y/ /#/ Elimine la lista de otros factores (innecesarios) (comentando)
  • bc Evaluar y mostrar aritméticamente

Pruébalo en línea!

Trauma digital
fuente
1
Es posible que pueda soltar el -r, y durante los dos primeros spuede usar /regex/cvaluepara jugar golf en un byte, simplificar aún más esta expresión regular puede ahorrar más, y puede guardar un byte en las últimas dos expresiones regulares reemplazando solo por :el /, y luego comentando la parte no deseada, así, tio.run/##JYlBCoMwFET3c4qABhdSfuZ/…
Kritixi Lithos
@Cowsquack muy bien, ¡gracias!
Trauma digital
1

Raqueta , 105 bytes

(λ(L)(map(λ(n)(if(< n 2)-1(p n(- n 1))))L))(define(p n d)(if(= d 1)1(if(=(modulo n d)0)d(p n(- d 1)))))

Pruébalo en línea!

Jonathan Frech
fuente
1

Befunge-98 (FBBI) , 39 bytes

j&:!+f0p1-1:::' -:!j;3k$.nbj;-\%!!j:1+a

Pruébalo en línea!

Termina con el &cuando no hay más números. Esto hace que el programa se detenga durante 60 segundos hasta que TIO finalice el programa. Esto es inevitable para Befunge-98, al menos en TIO porque ambos intérpretes hacen esto. Después de presionar play, puede detener el programa después de un momento para ver qué se generaría si esperara el minuto.


Esencialmente, para cada número nuevo, si es 0, lo convierte en 1. Luego pone un -1 en la pila seguido de un número que comienza desde 1 y cuenta hasta que alcanza el número de entrada, en cuyo caso imprime el segundo número en la pila (-1 para una entrada de 0 o 1, y el factor más alto para otros). Cada vez a través del ciclo, agregamos el valor del iterador a la pila detrás de él if ( input % iterator == 0). Esto significa que cuando lleguemos a la entrada, solo tenemos que tirar el iterador e imprimir. Luego, limpiamos la pila conn y volvemos a la función de entrada de lectura.

Puedo ampliar la explicación más tarde, ya veremos ...

Levemente Milquetoast
fuente
0

Retina 0.8.2 , 33 bytes

%(`^0|^1$
-1
\d+
$*
^(1+)\1+$
$.1

Pruébalo en línea! Link incluye aquellos casos de prueba que no son demasiado lentos. Explicación:

%(`

Pase sobre cada número de entrada.

^0|^1$
-1

Caso especial 0 y 1.

\d+
$*

Convierte a unario (no afecta a -1).

^(1+)\1+$
$.1

Reemplace cada número con su mayor factor propio en decimal.

Neil
fuente
0

tinylisp , 75 bytes

(load library
(q((L)(map(q((N)(i(l N 2)(- 1)(/ N(min(prime-factors N))))))L

Pruébalo en línea! (Contiene 4 bytes adicionales para dar un nombre a la función anónima para que podamos llamarla en el pie de página).

Ungolfed / explicación

Observe que devolver 1 para primo norte y el mayor factor menor que norte para composite norte se puede combinar para volver norte/ /pag dónde pag es el factor primo más pequeño de norte.

(load library)               Library gives us map, -, /, min, and prime-factors functions

(lambda (L)                  Anonymous function, takes a list of numbers L
 (map                         Map
  (lambda (N)                  Anonymous function, takes a number N
   (if (less? N 2)              If N < 2
    (- 1)                        -1; else
    (/ N                         N divided by
     (min                        the minimum
      (prime-factors N)))))      of the prime factors of N
  L)))                        ... to L
DLosc
fuente