A veces, cuando intento ociosamente factorizar cualquier número que aparezca delante de mí¹, después de un tiempo me doy cuenta de que es más fácil de lo que pensaba. Tomemos 2156por ejemplo: eventualmente se me ocurre que ambos 21y 56son múltiplos de 7, y ciertamente 2156 = 21 x 100 + 56también es un múltiplo de 7.

Su tarea es escribir un código que identifique números que sean más fáciles de factorizar debido a una coincidencia de este tipo.

Más precisamente:

Escriba un programa o función que tome un número entero positivo ncomo entrada y devuelva un valor verdadero si existe un divisor d(mayor que 1) tal que npueda cortarse en dos para obtener dos números enteros positivos, cada uno de los cuales es un múltiplo de d; devuelve un valor falso si no.

• "Picado en dos" significa lo que piensas: la representación habitual de base 10 de nparticionado en algún momento en una mitad frontal y una mitad posterior para producir otros dos enteros de base 10. Está bien si el segundo entero tiene un cero a la izquierda (pero tenga en cuenta que debe ser un entero positivo, por lo que dividirse 1230en 123y 0no es válido).
• Los valores de verdad y falsedad pueden depender de la entrada. Por ejemplo, si cualquier número entero distinto de cero es verdadero en el idioma de su elección, puede devolver el divisor do una de las "piezas" de n(o en nsí mismo).
• Por ejemplo, cualquier número par con al menos dos dígitos en el conjunto {2, 4, 6, 8}arrojará un valor verdadero: simplemente divídalo después del primer dígito par. También, por ejemplo, cualquier número primo narrojará un valor falso, al igual que cualquier número de un dígito.
• Tenga en cuenta que es suficiente considerar divisores primos d.
• Puede suponer que la entrada es válida (es decir, un entero positivo).

Este es el código de golf , por lo que gana el código más corto en bytes. Pero las soluciones en todos los idiomas son bienvenidas, por lo que podemos luchar por el código más corto en cada idioma, no solo el código más corto en general.

Casos de prueba

(Solo tiene que generar un valor verdadero o falso; las anotaciones a continuación son solo a modo de explicación). Algunas entradas que producen valores verdaderos son:

39  (3 divides both 3 and 9)
64  (2 divides both 6 and 4)
497  (7 divides both 49 and 7)
990  (splitting into 99 and 0 is invalid; but 9 divides both 9 and 90)
2233  (11 divides both 22 and 33)
9156  (3 divides both 9 and 156; or, 7 divides both 91 and 56)
11791  (13 divides both 117 and 91)
91015  (5 divides both 910 and 15)
1912496621  (23 divides both 1912496 and 621; some splittings are multiples of 7 as well)
9372679892  (2473 divides both 937267 and 9892; some splittings are multiples of 2 as well)

Algunas entradas que producen valores falsos son:

52
61
130  (note that 13 and 0 is not a valid splitting)
691
899
2397
9029
26315
77300  (neither 7730 and 0 nor 773 and 00 are valid splittings)
2242593803

¹ sí, realmente hago esto

Retina , 31 29 bytes

,$';$`
\d+
$*
;(11+)\1*,\1+;

Pruébalo en línea!

Emite un entero positivo para entradas válidas y cero para las inválidas.

No recomendaría esperar los casos de prueba más grandes ...

Explicación

,$';$`

En cada posición de la entrada, inserte una coma, luego todo antes de esa posición, luego un punto y coma, luego todo después de esta posición. Que hace eso Nos da todas las divisiones posibles de un número (dividido por ,, separado por ;), y luego la entrada nuevamente al final. Entonces la entrada se 123convierte

,123;1,23;12,3;123,;123
     ^     ^     ^

donde he marcado los caracteres de entrada originales (lo que no está marcado es lo que insertamos). Tenga en cuenta que esto crea divisiones no válidas que no son divisiones reales y tampoco le importa si el componente final es todo ceros, pero evitaremos aceptarlas más adelante. El beneficio de crear las divisiones no válidas es que sabemos que cada división válida tiene un ;frente y después, por lo que podemos guardar dos bytes en los límites de las palabras.

\d+
$*

Convierte cada número a unario.

;(11+)\1*,\1+;

Haga coincidir una división haciendo coincidir ambas mitades como múltiplos de algún número que sea al menos 2.

Brachylog (2), 8 bytes

~c₂ḋᵐ∋ᵐ=

Pruébalo en línea!

Explicación

~c₂ḋᵐ∋ᵐ=
~c₂       Split the input into two pieces
    ᵐ ᵐ   On each of those pieces:
   ḋ ∋      Choose a prime factor
       =  such that both the chosen factors are equal

Claramente, si el mismo número (mayor que 1) divide ambas piezas, el mismo número primo dividirá ambas. Requerir que el factor sea primo claramente deshabilita 1 como factor. También evita que 0se elija un literal como segmento de un número (porque 0no tiene factorización prima y provocará ḋun error).

No hay necesidad de verificar contra ceros internos coincidentes; Si una fracción de xy 0yes válida, x0y yfuncionará igual de bien (y en la otra dirección, si x0y yobras, ya que tenemos una solución de trabajo, independientemente de si xy 0yfuncionaría o no).

Un programa completo de Brachylog, como este, devuelve un booleano; true.si hay alguna forma de ejecutarlo sin fallas (es decir, hacer elecciones para que no ocurra ningún error), false.si todas las rutas conducen a fallas. Eso es exactamente lo que queremos aquí.

Jalea , 14 12 11 10 bytes

ŒṖḌo1g/€P>

¡Gracias a @JonathanAllan por jugar golf en 1 byte!

Pruébalo en línea!

Cómo funciona

ŒṖḌo1g/€P>  Main link. Argument: n

ŒṖ          Compute all partitions of n's decimal digits.
  Ḍ         Undecimal; convert each array in each partition back to integer.
   o1       OR 1; replace disallowed zeroes with ones.
     g/€    Reduce (/) each (€) partition by GCD (g).
            The last GCD corresponds to the singleton partition and will always be
            equal to n. For a falsy input, all other GCDs will be 1.
        P   Take the product of all GCDs.
         >  Compare the product with n.

Mathematica, 63 62 bytes

(1 byte gracias a Greg Martin)

1<Max@@GCD@@@Table[1~Max~#&/@Floor@{Mod[#,t=10^n],#/t},{n,#}]&

Es una función que toma un entero como entrada y devuelve Trueo False. Si lo prueba en un número grande, traiga un libro para leer mientras espera.

Explicación:

• Floor@{Mod[#,t=10^n],#/t}divide aritméticamente la entrada en sus últimos ndígitos y los m-ndígitos restantes (donde mes el número total de dígitos).
• Table[1~Max~#&/@...,{n,#}]hace esto para cada nhasta el número de entrada. (Esto es demasiado grande. Solo necesitamos hacer esto hasta el número de dígitos de la entrada, pero de esta manera ahorra bytes y aún así da el resultado correcto). El 1~Max~#&/@bit elimina los ceros, por lo que números como 130 -> {13,0}no cuentan como True.
• 1<Max@@GCD@@@... encuentra el máximo común divisor de cada uno de estos pares y comprueba si alguno de estos divisores es mayor que 1. Si lo son, hemos encontrado una manera de factorizar el número dividiéndolo.

Haskell , 57 bytes

x#n|b<-mod x n=x>n&&(b>0&&gcd(div x n)b>1||x#(10*n))
(#1)

Pruébalo en línea! Uso: (#1) 2156devoluciones TrueoFalse

C, 145 , 142, 139, 138, 135 bytes

i,a,b;f(){char s[99];scanf("%s",s);for(char*p=s;*p++;)for(b=atoi(p),i=*p,*p=0,a=atoi(s),*p=i,i=1;i++<b;)*s=a%i-b%i|b%i?*s:0;return!*s;}

JavaScript (ES6), 74 71 70 bytes

f=(s,t='',u)=>u?s%t?f(t,s%t,1):t:s&&f(t+=s[0],s=s.slice(1),1)>1|f(s,t)

<input oninput=o.textContent=f(this.value)><span id=o>

Toma la entrada como una cadena, que es útil para el fragmento. Editar: Guardado 3 bytes gracias a @ user81655.

Python 3, 133 118 117 bytes

i,j=int,input()
from fractions import*
print(any(i(j[k:])*i(j[:k])*~-gcd(i(j[k:]),i(j[:k]))for k in range(1,len(j))))

Ciertamente no es el más corto, probablemente podría acortarse un poco. Funciona a O(n)tiempo. La entrada se toma en formato \d+y la salida se da en formato (True|False)por defecto Valor booleano de Python
-3 bytes gracias a Dead Possum
-15 bytes gracias a ovs
-1 byte gracias a This Guy

QBIC , 91 90 bytes

;_LA|[a-1|B=left$(A,b)┘C=right$(A,a-b)┘x=!B!┘y=!C![2,x|~(x>1)*(y>1)*(x%c=0)*(y%c=0)|_Xq}?0

Explicación:

;               Get A$ from the command prompt
_LA|            Get the length of A$ and place it in a% (num var)
[a-1|           for b%=1; b% <= a%-1; b%++
B=left$(A,b)    break A$ in two components on index b%
C=right$(A,a-b)
x=!B!┘y=!C!     Convert both parts from string to num, assign to x% and y%
[2,x|           FOR c% = 2; c% <= x%; c%++

This next IF (~ in QBIC) is a bit ... iffy. It consists of a set of comparators.
Each comparator yields a -1 or a 0. We take the product of these. At any failed
comparison this will yield 0. When successful, it yields 1, which is seen as true by QBasic.

~(x>1)*(y>1)        IF X>1 and Y>1 --> this stops '00' and '1' splits.
*(x%c=0)*(y%c=0)    Trial divide the splits on loop counter c%.

|_Xq            Success? THEN END, and PRINT q (which is set to 1 in QBIC)
}               Close all language constructs (2 FOR loops and an IF)
?0              We didn't quit on match, so print 0

Python 3 , 70 69 bytes

import math
f=lambda n,d=1:n>d and n%d*~-math.gcd(n//d,n%d)+f(n,10*d)

Pruébalo en línea!

Perl 5 , 46 bytes

43 bytes de código + 3 bytes para -pbandera.

s~~$\|=grep!($`%$_|$'%$_),2..$`if$`*$'~ge}{

Pruébalo en línea! o pruebe esta versión modificada que permite múltiples entradas.
Probablemente no desee probar esto en la entrada más grande, ya que puede llevar un tiempo (muy largo).

Explicaciones:
iteramos a través de cada posición en la palabra con s~~~g, $`conteniendo los números antes y $'los números después. Si $`*$'es verdadero (significa que ninguno está vacío y ninguno lo está 0), entonces verificamos si un número entre 2 y los $`divide a ambos (con el grep!(...),2..$`). Si es así, $\|=..se establecerá $\en un valor distinto de cero, que se imprime implícitamente al final gracias a la -pmarca.

Python 2 , 69 bytes

f=lambda n,d=10,k=2:k<d<n and(n/d%k+n%d%k<1<n%d)|f(n,d,k+1)|f(n,10*d)

Utiliza la recursividad en lugar de los elementos integrados de GCD.

Pruébalo en línea!

Cómo funciona

Cuando se llama f con uno a tres argumentos ( d por defecto es 10 , k a 2 ), primero verifica el valor de la expresión k<d<n. Si las desigualdades k <d y d <n se mantienen, la siguiente expresión andse ejecuta y se devuelve su valor; de lo contrario, f simplemente devolverá False .

En el primer caso, comenzamos evaluando la expresión n/d%k+n%d%k<1<n%d.

d será siempre una potencia de diez, de modo n/dy n%defectivamente divide los dígitos decimales en n en dos rebanadas. Estas divisiones son divisibles por k si y solo si se n/d%k+n%d%kevalúa a 0 , que se prueba comparando el resultado con 1 .

Como parte de los requisitos es que ambos segmentos deben representar enteros positivos, el valor de n%dtambién se compara con 1 . Tenga en cuenta que 1 no tiene divisores primos, por lo que no se requiere la comparación más cara con 0 . Además, tenga en cuenta que d <n ya garantiza que n/dse evaluará a un entero positivo.

Finalmente, recursivamente todo f(n,d,k+1)(intentando el siguiente divisor común potencial) y f(n,10*d)(intentando la división) y devuelve el OR lógico de los tres resultados. Este medio f devolverá verdadero si (y solo si) k es un divisor común de n / d y n% d o el mismo es cierto para un valor mayor de k y / o un poder superior de diez d .