Às vezes, quando estou ociosamente tentando fatorar qualquer número que aparece na minha frente after, depois de um tempo percebo que é mais fácil do que eu pensava. Tome 2156por exemplo: que, eventualmente, ocorre-me que tanto 21e 56são múltiplos de 7e assim certamente 2156 = 21 x 100 + 56também é um múltiplo de 7.

Sua tarefa é escrever um código que identifique números mais fáceis de fatorar devido a uma coincidência desse tipo.

Mais precisamente:

Escreva um programa ou função que use um número inteiro positivo ncomo entrada e retorne um valor verdadeiro se existir um divisor d(maior que 1) que npossa ser dividido em dois para gerar dois números inteiros positivos, cada um dos quais é múltiplo d; retorne um valor falso se não.

• "Dividido em dois" significa o que você pensa: a representação usual da base 10 nparticionada em algum momento em uma metade da frente e uma metade traseira para produzir dois outros números inteiros da base 10. Tudo bem se o segundo inteiro tem um zero à esquerda (mas nota que ele deve ser um inteiro positivo, então a divisão 1230em 123e 0não é válido).
• Os valores de verdade e falsidade podem depender da entrada. Por exemplo, se qualquer número inteiro diferente de zero é verdadeiro no seu idioma de escolha, você pode devolver o divisor dou uma das "partes" de n(ou nela mesma nesse caso).
• Por exemplo, qualquer número par com pelo menos dois dígitos no conjunto {2, 4, 6, 8}produzirá um valor verdadeiro: basta dividi-lo após o primeiro dígito par. Também, por exemplo, qualquer número primo nproduzirá um valor falso, assim como qualquer número de um dígito.
• Observe que basta considerar os divisores principais d.
• Você pode assumir que a entrada é válida (ou seja, um número inteiro positivo).

Isso é código-golfe , então o código mais curto em bytes vence. Porém, soluções em todos os idiomas são bem-vindas, para que possamos buscar o código mais curto em cada idioma, não apenas o código mais curto em geral.

Casos de teste

(Você só precisa emitir um valor verdadeiro ou falso; as anotações abaixo são apenas uma explicação). Algumas entradas que produzem valores verdadeiros são:

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)

Algumas entradas que geram valores falsos são:

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

¹ sim, eu realmente faço isso

Retina , 31 29 bytes

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

Experimente online!

Emite um número inteiro positivo para entradas válidas e zero para entradas inválidas.

Eu não recomendaria esperar pelos casos de teste maiores ...

Explicação

,$';$`

Em cada posição da entrada, insira uma vírgula, tudo antes dessa posição, depois um ponto-e-vírgula e tudo depois dessa posição. O que isso faz? Ele nos fornece todas as divisões possíveis de um número (dividido por ,, separado por ;) e, em seguida, a entrada novamente no final. Então a entrada 123se torna

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

onde marquei os caracteres de entrada originais (o que não está marcado é o que inserimos). Observe que isso cria splitters inválidos que não são reais e também não se importa se o componente à direita é todos os zeros, mas evitaremos aceitá-los posteriormente. O benefício de criar divisões inválidas é que sabemos que cada divisão válida tem um ;na frente e depois dela, para que possamos salvar dois bytes nos limites da palavra.

\d+
$*

Converta cada número em unário.

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

Combine uma divisão, combinando as duas metades como múltiplos de algum número que seja pelo menos 2.

Braquilog (2), 8 bytes

~c₂ḋᵐ∋ᵐ=

Experimente online!

Explicação

~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, se o mesmo número (maior que 1) dividir as duas partes, o mesmo número primo dividirá as duas. Exigir que o fator seja primo desaprova ordenadamente 1 como um fator. Também impede que um literal 0seja escolhido como um segmento de um número (porque 0não possui fatoração primária e causará ḋfalha).

Não há necessidade de verificar se há zeros internos correspondentes; se uma divisão de xe 0yé válido, x0e yvai funcionar tão bem (e indo para o outro lado, se x0e yobras, então temos uma solução de trabalho, independentemente de xe 0yiria funcionar ou não).

Um programa completo do Brachylog, como este, retorna um booleano; true.se houver alguma maneira de executá-lo sem falha (por exemplo, para fazer escolhas que não ocorram erros), false.se todos os caminhos levarem à falha. É exatamente o que queremos aqui.

Geléia , 14 12 11 10 bytes

ŒṖḌo1g/€P>

Graças a @ JonathanAllan por jogar fora um byte!

Experimente online!

Como 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 graças a Greg Martin)

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

É uma função que recebe um número inteiro como entrada e retorna True ou False. Se você testá-lo em um número grande, leve um livro para ler enquanto espera.

Explicação:

• Floor@{Mod[#,t=10^n],#/t}divide aritmeticamente a entrada nos seus últimos ndígitos e nos m-ndígitos restantes (ondem é o número total de dígitos).
• Table[1~Max~#&/@...,{n,#}]faz isso para todos nos números de entrada. (Isso é muito grande. Só precisamos fazer isso até o número de dígitos da entrada, mas dessa maneira economiza bytes e ainda dá o resultado correto.) O 1~Max~#&/@bit se livra de zeros, portanto, números como 130 -> {13,0}não contam como True.
• 1<Max@@GCD@@@... encontra o maior divisor comum de cada um desses pares e verifica se algum desses divisores é maior que 1. Se forem, encontramos uma maneira de fatorar o número dividindo-o.

Haskell , 57 bytes

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

Experimente online! Uso: (#1) 2156retornos TrueouFalse

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>

Recebe a entrada como uma sequência, o que é útil para o snippet. Editar: salvou 3 bytes graças 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))))

Certamente não é o mais curto, provavelmente poderia ser reduzido um pouco. Funciona a O(n)tempo. A entrada é \d+recebida no formato e a saída é fornecida no formato (True|False)como valor booleano padrão do Python
-3 bytes, graças ao Dead Possum
-15 bytes, graças ao ovs
-1 byte, graças a Esse cara

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

Explicação:

;               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)

Experimente online!

Perl 5 , 46 bytes

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

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

Experimente online! ou tente esta versão modificada, permitindo várias entradas.
Você provavelmente não deseja tentar isso com a maior entrada, pois pode levar um tempo (muito longo).

Explicações:
Nós iteramos através de cada posição na palavra com s~~~g, $`contendo os números antes e $'depois. Se $`*$'for verdadeiro (significa que nenhum está vazio e nenhum está 0), então verificamos se um número entre 2 e $`divide os dois (com o grep!(...),2..$`). Nesse caso, $\|=..será definido $\como um valor diferente de zero, que é implicitamente impresso no final graças ao -psinalizador.

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)

Usa recursão em vez de incorporados ao GCD.

Experimente online!

Como funciona

Quando f é chamado com um a três argumentos ( d assume o padrão de 10 , k a 2 ), ele primeiro verifica o valor da expressão k<d<n. Se as desigualdades k <d e d <n forem mantidas, a expressão a seguir andserá executada e seu valor será retornado; caso contrário, f retornará False .

No primeiro caso, começamos avaliando a expressão n/d%k+n%d%k<1<n%d.

d sempre será uma potência de dez, portanto, n/de n%defetivamente divida os dígitos decimais em n em duas fatias. Essas fatias são divisíveis por k se e somente se forem n/d%k+n%d%kavaliadas como 0 , o que é testado comparando o resultado com 1 .

Como parte dos requisitos é que ambas as fatias devem representar números inteiros positivos, o valor de n%dtambém é comparado com 1 . Observe que 1 não possui divisores principais, portanto, a comparação mais cara com 0 não é necessária. Além disso, observe que d <n já garante quen/d será avaliado como um número inteiro positivo.

Finalmente, recursivamente tudo f(n,d,k+1)(tentando o próximo divisor comum em potencial) e f(n,10*d)(tentando a divisão) e retorna o OR lógico dos três resultados. Este meio f retornará verdadeiro se (e somente se) k é um divisor comum de n / d e n d% ou o mesmo é verdadeiro para um valor maior de k e / ou uma maior potência de dez d .