2013 tiene la factorización prima 3*11*61
. 2014 tiene la factorización prima 2*19*53
. Una propiedad interesante con respecto a estas factorizaciones es que existen números primos distintos en las factorizaciones de 2013 y 2014 que se suma al mismo número: 11+61=19+53=72
.
Escriba un programa o función que tome como entrada dos enteros positivos mayores que 1 y devuelva un valor verdadero si existe una suma de factores primos seleccionados de un número que sea igual a una suma de factores primos seleccionados en el segundo número, y un Falsey valor lo contrario.
Aclaraciones
- Se pueden usar más de dos factores primos. No todos los factores primos del número deben usarse en la suma. No es necesario que el número de primos usados de los dos números sea igual.
- Incluso si un primo se eleva a una potencia mayor que 1 en la factorización de un número, solo se puede usar una vez en la suma de primos para el número.
- 1 no es primo.
- Ambos números de entrada serán menores que
2^32-1
.
Casos de prueba
5,6
5=5
6=2*3
5=2+3
==>True
2013,2014
2013=3*11*61
2014=2*19*53
11+61=19+53
==>True
8,15
8=2^3
15=3*5
No possible sum
==>False
21,25
21=3*7
25=5^2
No possible sum (can't do 3+7=5+5 because of exponent)
==>False
Este es el código de golf. Aplican reglas estándar. El código más corto en bytes gana.
true
, ya que comparten el factor7
?Respuestas:
Julia,
9593 bytesLa función principal es
f
y llama a una función auxiliarg
.Sin golf:
Guardado 2 bytes gracias a Darth Alephalpha
fuente
map(p->map
es más corto que(m=map)(p->m
.Pyth, 11 bytes
Entrada en el formulario
30,7
.fuente
Pyth -
171211 bytesGracias a @FryAmTheEggman por corregir mi respuesta y guardar un byte.
Test Suite .
fuente
ty
obras y salva un adiós?Haskell,
115106bytesEjemplo de uso:
2013 # 2014
->True
.p
hace una lista de todos los factores primos de su argumento, elimina duplicados, hace una lista de todas las subsecuencias, elimina la primera (que siempre es la lista vacía) y finalmente suma las subsecuencias.#
comprueba sip a
no es igual a la diferenciap a \\ p b
. Si no son iguales, tienen al menos un elemento común.fuente
Japt, 25 bytes
Salidas
true
ofalse
. Pruébalo en línea!Sin golfos y explicación
Para obtener un byte adicional, puede dividir el código factorizar-único-combinar-suma entre ambas entradas, con la ventaja adicional de tener una complejidad de tiempo de
O(O(25-byte version)^2)
:fuente
CJam, 23 bytes
Pruébalo aquí.
El valor verdadero será concatenado todas las sumas comunes, el valor falso es la cadena vacía.
Explicación
fuente
Brachylog ,
109 bytesPruébalo en línea!
El predicado logra regresar
[the sum, the sum]
si existe, y falla si la suma no existe.-1 byte gracias a Fatalize (el creador de Brachylog) recordándome que existe el meta-predicado de verificación .
fuente
ᵛ - verify
lugar deˢ=
guardar un byte.MATL , 23 bytes
Utiliza la versión actual, 2.0.2 , que es anterior a este desafío.
Los números se proporcionan como dos entradas separadas. La salida es
0
o1
.Ejemplo
Explicación
fuente
Mathematica, 58 bytes
Explicación:
Esta es una función anónima.
Primero,
IntersectingQ
verifica si dos listas se cruzan. Pero las entradas son números en lugar de listas, por lo que permanece sin evaluar. Por ejemplo, si las entradas son2013
y2014
, luegoIntersectingQ@##&
regresaIntersectingQ[2013, 2014]
.Tr/@Rest@Subsets[#&@@@FactorInteger@#]&
es otra función anónima que toma un número entero, obtiene una lista de sus factores primos sin repeticiones, toma el conjunto de potencia, elimina el conjunto vacío y luego toma la suma de cada conjunto. EntoncesTr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]
vuelve{3, 11, 61, 14, 64, 72, 75}
.Luego mapea
Tr/@Rest@Subsets[#&@@@FactorInteger@#]&
sobre la expresiónIntersectingQ[2013, 2014]
.Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]
yTr/@Rest@Subsets[#&@@@FactorInteger@#]&[2014]]
son listas, para que podamos obtener el resultado de recopilación esta vez.fuente
IntersectingQ
primero es increíble! :)PARI / GP , 98 bytes
Factoriza, toma primos (
[,1]
), repite sobre subconjuntos no vacíos, suma y uniq, luego intersecta el resultado de esto para los dos números. El valor devuelto es el número de intersecciones, que es verdad a menos que sean 0fuente
APL (Dyalog Extended) ,
2317 bytes SBCS-5 gracias a ngn
Función de infijo tácito anónimo.
Pruébalo en línea!
⍥{
...}
aplique la siguiente función anónima a ambos argumentos:⍭
factores primos⍤
luego∪
los únicos de esos0+⍀.,
reducción de la tabla de suma de cero concatenada a cada factor∊
ϵ nlist (aplanar)∩
la intersección⍤
luego≢
el recuento de esos1<
¿hay más de uno? (uno porque las sumas de ningún factor)fuente
p+.×⊤1↓⍳2*≢p←
->1↓∊(⊢,+)/0,⍨
1↓∊∘.+/0,¨
1↓∊0∘.+.,
un producto interno - con qué frecuencia ves eso :)⍥
correctamente, esto también debería funcionar:1<∘≢∩⍥{∊0∘.+.,∪⍭⍵}
05AB1E ,
108 bytes-2 bytes gracias a @Emigna .
Pruébelo en línea o verifique todos los casos de prueba .
Explicación:
fuente
f€æO`å¦à
debería funcionar para 8.Japt, 12 bytes
Ejecútalo en línea
fuente
Python 3 , 206 bytes
Esta es una función lambda (m), que toma 2 números y devuelve un conjunto que contiene cualquier suma de factores primos que tengan en común. En Python, este es un valor verdadero cuando no está vacío, y un valor falso cuando está vacío.
Editar: Resulta que mi respuesta original no funcionó para las entradas principales, como lo señaló @JoKing. Esto se ha solucionado (junto con algunos otros errores) a un costo trágico de 40 bytes.
Explicación rápida usando comentarios:
Pruébalo en línea!
fuente
5,6
, ya que no maneja entradas principalesAPL (NARS), 50 caracteres, 100 bytes
aquí π encontraría la matriz de factores en su argumento;
sería la función que encuentra todos los subconjuntos ... tengo que decir que parece {⍵operator itsArguments} ¨ (para cada izquierda) y ¨ (para cada derecha) pueden imitar el bucle con un número fijo de ciclos y ¨¨ está bien en para ver subconjuntos de un conjunto ... esta forma de ver parece reducir los símbolos en los bucles de descripción ...; prueba
Un pequeño análisis:
fuente
Japt
-¡
, 14 bytesGuardado 3 bytes gracias a @Shaggy
Intentalo
fuente
ÎfUÌ l
o, más corto todavía,rf l
.rø
sería la forma más corta de hacerlo, pero Oliver te ganó.Jalea ,
189 bytesPruébalo en línea!
Gracias a @Jonathan Allan por -9 y la increíble ayuda :).
Toma la entrada como una matriz de dos elementos. Explicación del código:
¹
fuente
,
. ElẒƇ
es redundante, no hay factores primos no primos. EntoncesÆFḢ€
es justoÆf
, excepto que este último nos da las repeticiones que realmente podríamos necesitar, por ejemplo26=2*13
y125=5*5*5
mientras2+13=5+5+5
. Sin embargo, incluso con eso,Ẇ
no es lo suficientemente bueno, por ejemplo, en lugar de26
usar,182=2*7*13
que también debería encontrar eso,2+13=5+5+5
pero no lo hace; en su lugar, queremos el conjunto de potencia (ŒP
) sin el elemento inicial, vacío, (podemos usarḊ
).S€
aquí puede ser reemplazado con§
. - Probablemente pueda guardar bytes con$
yƊ
-.)
y con mis correcciones para hacer que funcione correctamente (además de la sustituciónœ&
conf
) el código de bytes es de 9:ÆfŒPḊ§)f/
try-itGaia ,
1611 bytesPruébalo en línea!
La función superior (primera línea) calcula las sumas del conjunto de potencia de los factores primos, y la segunda función determina si alguno de los elementos de la intersección no es cero.
fuente