De todos los años que llevo haciendo este desafío, 2017 es el primer año que ha sido un número primo. Entonces la pregunta será sobre los números primos y sus propiedades.
Su tarea es producir un programa o función que tome un entero positivo arbitrariamente grande como entrada, y genere o devuelva si el número es 2.017-friable , es decir, si el factor primo más grande en ese número es 2.017 o menos.
Algunos ejemplos de entradas y sus salidas:
1 (has no prime factors)
true
2 (= 2)
true
80 (= 2 x 2 x 2 x 2 x 5)
true
2017 (= 2017)
true
2019 (= 3 x 673)
true
2027 (= 2027)
false
11111 (= 41 x 271)
true
45183 (= 3 x 15061)
false
102349 (= 13 x 7873)
false
999999 (= 3 x 3 x 3 x 7 x 11 x 13 x 37)
true
1234567 (= 127 x 9721)
false
4068289 (= 2017 x 2017)
true
Su programa no tiene que emitir literalmente true
y false
- cualquier valor verdadero o falso, y de hecho, dos salidas diferentes que sean consistentes entre los casos verdadero y falso están bien.
Sin embargo, no puede usar ningún primo en su código fuente. Los premios vienen en dos tipos:
Caracteres, o secuencias de caracteres, que representan literales de números primos.
Los personajes
2
,3
,5
, y7
son ilegales en lenguas cuando los números son símbolos válidos.El número
141
es ilegal porque contiene41
, aunque sea válido1
y de4
otra manera.Los caracteres
B
yD
(ob
yd
) son ilegales en los idiomas en los que generalmente se usan como 11 y 13, como CJam o Befunge.
Caracteres que tienen valores Unicode con valores primos o que contienen bytes con valores primos en su codificación.
Los caracteres
%)+/5;=CGIOSYaegkmq
son ilegales en ASCII, así como el carácter de retorno de carro.El carácter
ó
es ilegal en UTF-8 porque tiene su codificación0xb3
. Sin embargo, en ISO-8859-1, su codificación es simple0xf3
, que es compuesta y, por lo tanto, está bien.
El código más corto para hacer lo anterior en cualquier idioma gana.
=
reglas descarta la mayoría de los idiomas estándar ...Respuestas:
Jalea , 8 bytes
Pruébalo en línea! Tenga en cuenta que los casos de prueba 11111 y superiores son demasiado para TIO.
Verificación
El caso de prueba 999999 ha estado funcionando durante 13 horas. ¡Soy pesimista sobre la informática 2025! 4068289 ...
Cómo funciona
fuente
(2^n)!
. Esto también sirve para entradas de seis tamaños, pero al menos las entradas están en un alfabeto decimal en lugar de uno binario.Gelatina , 8 caracteres, 14 bytes de UTF-8
Pruébalo en línea!
Jelly normalmente usa su propia página de códigos para los programas. Sin embargo, la mayoría de sus incorporaciones relacionadas con los principales comienzan con
Æ
, que es el punto de código 13; No muy útil. Afortunadamente, el intérprete también es compatible con UTF-8, que tiene una codificación más amigable.Verificación
Este programa, en UTF-8, hexdumps como este:
Verificación de que todos los bytes son compuestos:
Verificación de que todos los puntos de código Unicode son compuestos:
El único token analizado como un número es
90
. Ninguno de9
,0
y90
son primos.Explicación
La idea matemática principal aquí es que 45² es 2025, que cae claramente entre 2017 (el año actual) y 2027 (el próximo primer año). Por lo tanto, podemos sacar la raíz cuadrada de cada factor primo del número y ver si alguno excede 45. Desafortunadamente, no podemos escribir
45
debido al literal5
, por lo que tenemos que duplicarlo y compararlo con 90.fuente
u
es compuesta, por lo que solo sería una cuestión de cambiar el puntaje en lugar de algo que lo invalide.)Mathematica,
625855 bytes¡Los últimos tres bytes guardados se deben totalmente a Martin Ender!
Función sin nombre que toma un argumento entero positivo y devuelve
True
oFalse
.Algoritmo recursivo,
#4<4
siendo el caso base verdadero (solo necesitamos que regreseTrue
a la entrada 1, pero los casos base adicionales están bien). De lo contrario, calculamos el segundo divisor más pequeño (que es necesariamente primo) de la entrada conDivisors[#][[6-4]]
; si es mayor que 2024 (44*46
), salimos conFalse
, de lo contrario llamamos a la función de forma recursiva (usando#6
set to#0
) en la entrada dividida por este pequeño factor primo#
(que tenemos que expresar como#^-1
veces la entrada#4
, ya/
que no está permitido).Estructuralmente, la primera parte
#4<4||#<44*46&[#^-1#4]&
es una función anónima de seis argumentos, siendo llamado con argumentosDivisors[#][[6-4]]
,Null
,Null
,#
,Null
, y#0
; esto es para moverse por la prohibición de los personajes2
,3
y5
.Versión anterior, que ahorró cuatro bytes al reemplazar
8018-6000
con44*46
, inspirada en la respuesta Jelly de ais523 (Martin Ender también parecía inspirado por un comentario de ais523):Esto fue bastante desagradable: ¡todavía no sé cómo establecer una variable en Mathematica bajo estas restricciones! Ambos
=
y los dee
adentroSet
están prohibidos. Evitar+
y)
también fue un problema, pero no demasiado difícil de solucionar a expensas de más bytes.fuente
#2
también sería anulado, por lo que tendría que tener cuidado con la forma en anidar sus lambdas, y la falta de paréntesis, podría hacer que difícil.)#4<4||#<44*46&[#^-1#4]&[Divisors[#][[6-4]],,,#,,#0]&
arroja un montón de advertencias porque ahora lo intentaDivisors[#][[2]]
antes de asegurarse de que la entrada sea mayor que 1 (o 3), pero el resultado sigue siendo correcto.Haskell,
4847 bytesBásicamente una traducción de la respuesta de Dennis 'Jelly . xnor guardó un byte.
Se usa
[…]!!0
como paréntesis porque)
está prohibido ysnd
+divMod
porque está prohibidom
inmod
yrem
.fuente
!!0<1
con<[1]
. Pero parece que está en corto para usardiv
como[\p n->p^n`div`n*n>p^n-1]!!0$product[1..44*46]
.\n->[0|p<-[product[1..44*46]^n],0<-[p,p-n..0]]
qué usos que las salidas solo necesitan ser consistentes.Pyke,
10879 bytesPruébalo aquí!
Se guardó 1 byte utilizando la forma de Dennis de generar 2025
fuente
Brachylog ,
910 bytesPruébalo en línea!
Básicamente usando el mismo algoritmo que mi otra respuesta.
$ph
encuentra el primer (h
) factor primo ($p
); Este es el factor primo más grande, ya que las listas de factores primos de Brachylog van de mayor a menor. Luego tomo la raíz cuadrada ($r
), doble (*
), y pruebo si es menor que 90 (<90
).Primero tuve que duplicar la entrada porque 1 no tiene factores primos (y, por lo tanto, no tiene primer factor primo). Esto agrega un factor primo adicional de 2, que no puede afectar si un número es friable en 2017, pero evita una falla al manejar 1.
fuente
En realidad , 9 bytes
¡Gracias a Dennis por muchos bytes!
Pruébalo en línea!
Explicación:
fuente
Mathematica,
6674 bytesGracias a Dennis por señalar que
U+F4A1
está prohibido.Explicación:
Divisors@#
: Lista de divisores enteros del primer argumento#
.0<1
: Golf paraTrue
(también evita el uso de la letrae
).Divisors@d^0
: Lista de la forma{1, 1, ..., 1}
con longitud igual al número de divisores ded
.Tr
: Para una lista plana,Tr
devuelve la suma de esa lista. Por lo tanto,Tr[Divisors@d^0]
devuelve el número de divisores ded
.Function[{x,d},And[x,Tr[Divisors@d^0]>6-4||d<44*46]]
: Función anónima con dos argumentosx
yd
. La idea es qued
es un divisor de#
y probamos para ver si es compuesto o menor o igual que2017
(inclusive).2017
-friabilidad es equivalente a todos los divisores que satisfacen esta condición. Como ais523 descubrió, ser un primo menor o igual a2017
es equivalente a ser un primo menor que2025
. Como Greg Martin señaló, es suficiente probar si es menor que2024=44*46
. El argumentox
actúa como un acumulador para determinar si todos los divisores encontrados hasta ahora satisfacen esta propiedad. Luego dejamosFold
esta función a través de todos los divisores de#
con valor inicialTrue
, Ya que tenemos acceso ni aMap
ni/@
.fuente
05AB1E , 10 bytes
Devuelve 1 si es verdadero, 0 de lo contrario.
Pruébalo en línea!
Explicación
fuente
MATL , 15 bytes
Salidas
0
para no-2017-friable o1
para 2017-friable.Pruébalo en línea! O verificar todos los casos de prueba .
Este programa verifica que todos los bytes sean compuestos.
Explicación
fuente
Bash, 144 bytes
Codificación ASCII:
Como de costumbre para el shell, el código de salida indica éxito (0) o falla (no 0).
Esto es efectivamente una ortografía diferente de
Obtenemos el factor más grande con
factor $1|grep -o '[0-9]*$'
; eltr -d :
es un caso especial para input =1
.La expresión se
$[6*6*69-466]
evalúa a 2018.Fue complicado usar
tr
los nombres de los comandos y aún usar la sustitución de comandos: no pude usar el formulario de anidación$( )
, así que terminé conectando con otro Bash para evaluar el resultado.Resultados de la prueba:
Confirmación de códigos de caracteres:
fuente
Pyth, 11 bytes
Pruébalo en línea. Banco de pruebas.
Utiliza el truco de Dennis para obtener 2025, luego verifica si no hay factores primos de entrada mayores.
fuente
Julia 0.4 ,
843837 bytesEspera un BigInt como argumento.
Pruébalo en línea! o verificar que ningún byte sea primo .
fuente
Japt , 14 bytes
Devuelve 1 si es verdadero, 0 si es falso.
Probarlo aquí .
fuente
k
tiene un valor primoBraingolf , 11 bytes [muy poco competitivo]
Pruébalo en línea!
No se puede leer debido a
ߢ
que se atornilla con los números, sin embargo, todavía funciona en un intérprete.Ni siquiera noté las restricciones de caracteres cuando escribí esto, pero todo lo que tuve que hacer fue cambiar el extraño carácter unicode de 2017 a 2018.
Dado que 2018 no es primo, cualquier primo
<= 2018
también lo es<= 2017
Explicación
fuente