Um número inteiro gaussiano é um número complexo cujas partes reais e imaginárias são números inteiros.
Inteiros gaussianos, como inteiros comuns, podem ser representados como um produto de números primos gaussianos, de uma maneira única. O desafio aqui é calcular os constituintes principais de um dado inteiro gaussiano.
Entrada: um número inteiro gaussiano, que não é igual a 0 e não é uma unidade (ou seja, 1, -1, iei não podem ser dados como entradas). Use qualquer formato sensível, por exemplo:
- 4-5i
- -5 * j + 4
- (4, -5)
Saída: uma lista de números inteiros gaussianos, que são primos (ou seja, nenhum deles pode ser representado como um produto de dois números inteiros gaussianos não unitários) e cujo produto é igual ao número de entrada. Todos os números na lista de saída devem ser não triviais, ou seja, não 1, -1, i ou -i. Qualquer formato de saída sensível pode ser usado; não deve necessariamente ser o mesmo que o formato de entrada.
Se a lista de saída tiver mais de 1 elemento, serão possíveis várias saídas corretas. Por exemplo, para a entrada 9, a saída pode ser [3, 3] ou [-3, -3] ou [3i, -3i] ou [-3i, 3i].
Casos de teste (extraídos desta tabela ; 2 linhas por caso de teste)
2
1+i, 1-i
3i
3i
256
1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i
7+9i
1+i,2−i,3+2i
27+15i
1+i,3,7−2i
6840+585i
-1-2i, 1+4i, 2+i, 3, 3, 6+i, 6+i
Funções internas para fatorar números inteiros gaussianos não são permitidas. No entanto, é permitido levar em consideração números inteiros comuns por funções internas.
fonte
3i
retornar como3,i
ou3i
?3i
é a resposta correta porquei
não é primo. Atualizei o caso de teste para torná-lo mais claro.6840+585i
tem a lista errada de fatores, pois5
não é um primo gaussiano. Em vez disso, ele retorna-1-2i, 1+4i, 2+i, 3, 3, 6+i, 6+i
. Fonte256=(1+i)**16
não(1+i)**8
porque256=2**8=(2i)**8
e2i=(1+i)**2
Respostas:
Geléia ,
6155 bytesExperimente online! (Cabeçalho e rodapé formata a saída)
-6 bytes graças a @EricTheOutgolfer
Como funciona
fonte
Rubi ,
258256249246 + 8 =264257254 bytesUsa a
-rprime
bandeira.Nossa, que bagunça.
Usa esse algoritmo do stackoverflow.
Experimente online!
fonte
Python 2 ,
250239223215 bytesExperimente online!
(a,b)
Alguma explicação decompõe recursivamente um complexo em dois complexos até que nenhuma decomposição seja possível ...
fonte
def f(Z,s=[])
você deve economizar um personagemFerrugem - 212 bytes
Não tenho 100% de certeza se isso funciona 100% correto, mas parece estar correto para uma grande variedade de testes. Isso não é menor que o Jelly, mas pelo menos é menor que as linguagens interpretadas (até agora). Também parece ser mais rápido e pode trabalhar com entradas de um bilhão de magnitude em menos de um segundo. Por exemplo, 1234567890 + 3141592650i fatores como (-9487 + 7990i) (- 1 + -1i) (- 395 + 336i) (2 + -1i) (1 + 1i) (3 + 0i) (3 + 0i) (4+ 1i) (- 1 + 1i) (- 1 + 2i), (clique aqui para testar o wolfram alpha)
Isso começou como a mesma idéia do fatoração ingênua de números inteiros, para passar por cada número abaixo do número inteiro em questão, ver se ele se divide, repetir até terminar. Então, inspirado por outras respostas, ele se transformou ... fatores repetidamente fatores em um vetor. Faz isso um bom número de vezes, mas não 'até' qualquer coisa. O número de iterações foi escolhido para cobrir uma boa parte das entradas razoáveis.
Ele ainda usa "(a mod b) == 0" para testar se um número inteiro divide outro (para Gaussianos, usamos o módulo gaussiano Rust interno e consideramos "0" como norma == 0), no entanto, verifique a 'norma ( a / b)! = 1 'evita dividir "demais", basicamente permitindo que o vetor resultante seja preenchido apenas com números primos, mas não levando nenhum elemento do vetor à unidade (0-i, 0 + i, -1 + 0i, 1 + 0i) (que é proibido pela pergunta).
Os limites do loop for foram encontrados através do experimento. y vai de 1 para cima para evitar pânico de dividir por zero ex pode ir de -999 a 0, graças ao espelhamento de gaussianos sobre os quadrantes (acho?). Quanto às limitações, a pergunta original não indicava um intervalo válido de entrada / saída, portanto, é assumido um "tamanho de entrada razoável" ... (Editar ... no entanto, não sei exatamente como calcular em que número isso será começar a "falhar", imagino que existem números inteiros gaussianos que não são divisíveis por nada abaixo de 999, mas ainda são surpreendentemente pequenos para mim)
Experimente a versão um pouco desacreditada em play.rust-lang.org
fonte
Perl 6 ,
141124 bytesAgradecimentos a Jo King por -17 bytes
Experimente online!
fonte
floor
parte está verificando se$_/w
(ou seja, o fator atual dividido por um número) é um número inteiroPitão ,
5451454236 bytesExperimente online!
Aceita entrada no formulário
1+2j
- números puramente reais ou imaginários podem omitir o outro componente (por exemplo9
,2j
). Saída é uma lista separada por nova linha de números complexos, na forma(1+2j)
, com números puramente imaginários omitindo a parte real.Isso usa divisão de trilha simples, gerando todos os números inteiros gaussianos com magnitude maior que 1 e menor que o valor atual, mais o próprio valor. Eles são filtrados para manter aqueles que são um fator do valor, e o menor por magnitude é escolhido como o próximo fator principal. Isso é gerado e o valor é dividido por ele para produzir o valor para a próxima iteração.
Além disso, Pyth vence Jelly 😲 (não espero que dure)
fonte