Esse número é primo?

195

Acredite ou não, ainda não temos um desafio de golfe por código para um simples teste de primalidade . Embora possa não ser o desafio mais interessante, principalmente para idiomas "comuns", pode não ser trivial em muitos idiomas.

O código Rosetta apresenta listas por idioma de abordagens idiomáticas para o teste de primalidade, uma usando o teste de Miller-Rabin especificamente e outra usando a divisão de teste . No entanto, "a maioria dos idiomáticos" geralmente não coincide com a "mais curta". Em um esforço para tornar o Programming Puzzles e o Code Golf o site de referência para o code-golf, esse desafio busca compilar um catálogo da abordagem mais curta em todos os idiomas, semelhante a "Olá, Mundo!" e Golf um quine para o bem! .

Além disso, a capacidade de implementar um teste de primalidade faz parte da nossa definição de linguagem de programação , portanto esse desafio também servirá como um diretório de linguagens de programação comprovadas.

Tarefa

Escreva um programa completo que, dado um número inteiro estritamente positivo n como entrada, determine se n é primo e imprima um valor verdadeiro ou falso de acordo.

Para o objetivo desse desafio, um número inteiro é primo se tiver exatamente dois divisores estritamente positivos. Observe que isso exclui 1 , que é seu único divisor estritamente positivo.

Seu algoritmo deve ser determinístico (isto é, produzir a saída correta com probabilidade 1) e deve, em teoria, funcionar para números inteiros arbitrariamente grandes. Na prática, você pode assumir que a entrada pode ser armazenada no seu tipo de dados, desde que o programa funcione para números inteiros de 1 a 255.

Entrada

  • Se seu idioma puder ler de STDIN, aceitar argumentos de linha de comando ou qualquer outra forma alternativa de entrada do usuário, você poderá ler o número inteiro como sua representação decimal, representação unária (usando um caractere de sua escolha), matriz de bytes (grande ou little endian) ou byte único (se esse for o maior tipo de dados do seu idioma).

  • Se (e somente se) seu idioma não puder aceitar qualquer tipo de entrada do usuário, você poderá codificá-la no seu programa.

    Nesse caso, o número inteiro codificado permanentemente deve ser facilmente trocável. Em particular, ele pode aparecer apenas em um único local em todo o programa.

    Para fins de pontuação, envie o programa que corresponde à entrada 1 .

Resultado

A saída deve ser gravada em STDOUT ou na alternativa mais próxima.

Se possível, a saída deve consistir apenas em um valor verdadeiro ou falso (ou uma representação de string), opcionalmente seguido por uma única nova linha.

A única exceção a essa regra é a saída constante do intérprete do seu idioma que não pode ser suprimida, como uma saudação, códigos de cores ANSI ou recuo.

Regras adicionais

  • Não se trata de encontrar o idioma com a abordagem mais curta para testes principais, trata-se de encontrar a abordagem mais curta em todos os idiomas. Portanto, nenhuma resposta será marcada como aceita.

  • Os envios na maioria dos idiomas serão pontuados em bytes em uma codificação preexistente apropriada, geralmente (mas não necessariamente) UTF-8.

    O idioma Piet , por exemplo, será pontuado em codels, que é a escolha natural para esse idioma.

    Alguns idiomas, como pastas , são um pouco difíceis de pontuar. Em caso de dúvida, pergunte no Meta .

  • Diferentemente de nossas regras usuais, fique à vontade para usar um idioma (ou versão do idioma), mesmo que seja mais novo que esse desafio. Se alguém quiser abusar disso criando uma linguagem em que o programa vazio realiza um teste de primalidade, parabéns por abrir caminho para uma resposta muito chata.

    Observe que deve haver um intérprete para que o envio possa ser testado. É permitido (e até encorajado) escrever esse intérprete para um idioma anteriormente não implementado.

  • Se o seu idioma de escolha for uma variante trivial de outro idioma (potencialmente mais popular) que já tenha uma resposta (pense em dialetos BASIC ou SQL, shell do Unix ou derivados triviais do Brainfuck como Headsecks ou Unary), considere adicionar uma nota à resposta existente que a mesma solução ou uma solução muito semelhante também é a mais curta no outro idioma.

  • Funções internas para testar a primalidade são permitidas. Esse desafio visa catalogar a solução mais curta possível em cada idioma; portanto, se for mais curto usar um built-in em seu idioma, tente.

  • A menos que tenham sido anuladas anteriormente, todas as regras padrão de código de golfe se aplicam, incluindo o http://meta.codegolf.stackexchange.com/q/1061 .

Como uma observação lateral, por favor, não reduza as respostas chatas (mas válidas) em idiomas onde não há muito para jogar golfe; eles ainda são úteis para essa pergunta, pois ele tenta compilar um catálogo o mais completo possível. No entanto, primariamente upvote respostas em idiomas onde o autor realmente teve que se esforçar para jogar o código no golfe.

Catálogo

O snippet de pilha na parte inferior desta postagem gera o catálogo a partir das respostas a) como uma lista da solução mais curta por idioma eb) como uma tabela geral de líderes.

Para garantir que sua resposta seja exibida, inicie-a com um título, usando o seguinte modelo de remarcação:

## Language Name, N bytes

onde Nestá o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Se você quiser incluir vários números no cabeçalho (por exemplo, porque sua pontuação é a soma de dois arquivos ou você deseja listar as penalidades do sinalizador de intérpretes separadamente), verifique se a pontuação real é o último número no cabeçalho:

## Perl, 43 + 2 (-p flag) = 45 bytes

Você também pode transformar o nome do idioma em um link que será exibido no snippet:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

Mostrar snippet de código

code-golf number number-theory primes decision-problem Dennis
fonte
Posso aceitar entradas como números negativos, onde abs (entrada) seria o número que estou testando?
Stan Strum
Não, a entrada é um número inteiro estritamente positivo.
Dennis
11
@LyndonWhite Isso foi concebido como um catálogo (como "Olá, Mundo!" ) De testes de primalidade, portanto, um formato de envio unificado parecia preferível. Lamento uma das duas decisões sobre esse desafio, sendo a outra apenas permitindo testes de primalidade determinísticos.
Dennis
11
@ Shaggy Parece uma pergunta para meta.
Dennis
11
Sim, era isso que eu estava pensando. Vou deixar você fazer as honras, já que é o seu desafio.
Shaggy

Respostas:

226

Olá Mundo! 13

hello, world!
histocrata
fonte
83
Você acabou de criar esse idioma, apenas para este envio? ;)
ETHproductions
41
@ETHproductions Parece que o commit mais recente ocorreu 10 dias atrás.
Geobits
39
Eu esperava ter o idioma em uma forma um pouco melhor antes de vinculá-lo a qualquer lugar, mas esse desafio foi publicado e não pude resistir.
histocrat 11/09/2015
31
Eu quase diria que pendurar em uma entrada 1 é a funcionalidade correta.
Iamnotmaynard # 14/15
22
A melhor parte disso é que o programa não é apenas um built-in, cada personagem desempenha seu próprio papel na obtenção do resultado correto.
ETHproductions
157

Hexagonia , 29 bytes

.?'.).@@/'/.!.>+=(<.!)}($>(<%

A versão legível deste código é:

   . ? ' .
  ) . @ @ /
 ' / . ! . >
+ = ( < . ! )
 } ( $ > ( <
  % . . . .
   . . . .

Explicação: Teste se existe um número de 2 a n-1 que divide n.

Inicialização:

Escreva n em uma célula de memória e n-1 em outra:

   . ? ' .
  . . . . .
 . . . . . .
+ = ( . . . .
 . . . . . .
  . . . . .
   . . . .

Caso Especial n = 1:

Imprima um 0 e termine

   . . . .
  . . . @ .
 . . . ! . .
. . . < . . .
 . . . . . .
  . . . . .
   . . . .

O laço

Calcule n% a e diminua a. Termine se a = 1 ou n% a = 0.

   . . . .
  ) . . . /
 ' / . . . >
. . . . . . .
 } ( $ > ( <
  % . . . .
   . . . .

Caso a = 1:

Aumente de 0 a 1, imprima e finalize. (O ponteiro de instrução corre na direção NE e passa do canto leste ao canto sudoeste. E o $ certifica-se de que ignora o próximo comando)

   . . . .
  . . . @ .
 . . . ! . .
. . . < . . )
 . . $ . . <
  . . . . .
   . . . .

Caso a% n = 0:

Imprima o 0 e termine (o ponteiro da instrução está executando SW e passa para o topo para o @

   . . . .
  . . @ . .
 . . . . . >
. . . . . ! .
 . . . . . .
  . . . . .
   . . . .
Etoplay
fonte
61
Caramba, esse é um primeiro post impressionante. :) Colocarei a recompensa agora (concederei em 7 dias, para chamar mais atenção à sua resposta). Bem-vindo ao PPCG!
Martin Ender
35
Ótima resposta! +1 para " A versão legível deste código é: <...> " :-)
agtoever
68

Hexagonia , 218 92 58 55 bytes

Aviso: Esta resposta foi solidamente batida com uma solução de lado 4 da Etoplay.

)}?}.=(..]=}='.}.}~./%*..&.=&{.<......=|>(<..}!=...&@\[

O primeiro programa Hexagony não trivial (ou seja, não linear)! É baseado na mesma abordagem fatorial ao quadrado da resposta Labirinto do Sp3000 . Depois de começar com um hexágono de tamanho 10, eu consegui comprimi-lo para baixo para o tamanho 5. No entanto, eu era capaz de reutilizar algum código duplicado e ainda há muito um bando de sem-ops no código, de modo que o tamanho 4 pode apenas seja possível.

Explicação

Para entender o código, primeiro precisamos desdobrá-lo. O hexagony coloca qualquer código-fonte no próximo número hexagonal centralizado com no-ops ( .), que é 61. Em seguida, reorganiza o código em um hexágono regular do tamanho correspondente:

     ) } ? } .
    = ( . . ] =
   } = ' . } . }
  ~ . / % * . . &
 . = & { . < . . .
  . . . = | > ( <
   . . } ! = . .
    . & @ \ [ .
     . . . . .

Isso é bastante disputado com caminhos de execução cruzados e sobrepostos e vários ponteiros de instrução (IPs). Para explicar como funciona, vamos primeiro ver uma versão não-gasta em que o fluxo de controle não passa pelas bordas, apenas um IP é usado e os caminhos de execução são os mais simples possíveis:

             . . . . . . . . . . . . .
            . . . . . . . . . . . . . .
           . . . . . . . . . . . . . . .
          . . . . . . . . . . @ . . . . .
         . . . . . . . . . . ! . . . . . .
        . . . . . . . . . . % . . . . . . .
       . . . . . . . . . . ' . . . . . . . .
      . . . . . . . . . . & . . . . . . . . .
     . . . . . . . . . . { . . . . . . . . . .
    . . . . . . . . . . * . . . . . . . . . . .
   . . . . . . . . . . = . . . . . . . . . . . .
  . . . . . . . . . . } . . . . . . . . . . . . .
 ) } ? } = & { < . . & . . . . . . . . . . . . . .
  . . . . . . . > ( < . . . . . . . . . . . . . .
   . . . . . . = . . } . . . . . . . . . . . . .
    . . . . . } . . . = . . . . . . . . . . . .
     . . . . | . . . . | . . . . . . . . . . .
      . . . . * . . . ) . . . . . . . . . . .
       . . . . = . . & . . . . . . . . . . .
        . . . . > } < . . . . . . . . . . .
         . . . . . . . . . . . . . . . . .
          . . . . . . . . . . . . . . . .
           . . . . . . . . . . . . . . .
            . . . . . . . . . . . . . .
             . . . . . . . . . . . . .

Nota lateral: o código acima começa com a execução da primeira linha, cheia de no-ops. Então, quando o IP atinge a borda nordeste, ele quebra no canto mais à esquerda (a )), onde o código real começa.

Antes de começarmos, uma palavra sobre o layout da memória do Hexagony. É um pouco como a fita de Brainfuck em esteróides. Na verdade, não é uma fita, mas é uma grade hexagonal em si (uma infinita), onde cada aresta tem um valor inteiro, que é inicialmente 0 (e, em oposição ao Brainfuck padrão, os valores são assinados com números inteiros de precisão arbitrária). Para este programa, usaremos quatro arestas:

insira a descrição da imagem aqui

Vamos calcular o fatorial na borda Um , contagem decrescente a nossa entrada na borda C e armazenar outra cópia da entrada (para o módulo) na borda D . B é usado como uma aresta temporária para cálculos.

O ponteiro de memória (MP) começa na borda A e aponta para o norte (isso é importante para mover o MP). Agora, aqui está o primeiro bit do código:

)}?}=&{

)incrementa a aresta A até 1a base do fatorial. }faz com que o MP vire à direita, ou seja, vá para a borda C (apontando para nordeste). Aqui lemos a entrada como um número inteiro com ?. Em seguida, damos mais um turno direito de borda D com }. =inverte a MP, de tal forma que ele aponta no vértice compartilhado com C . &copia o valor de C (a entrada) para D - o valor é copiado da esquerda porque o valor atual não é positivo (zero). Finalmente, fazemos o MP virar à esquerda para C com {.

Em seguida, <tecnicamente é um ramo, mas sabemos que o valor atual é positivo, portanto o IP sempre girará à direita em direção ao >. Um galho bateu de atos secundários como um espelho, de modo que o IP se move horizontalmente, novamente, para o (que diminui o valor em C .

O próximo ramo, na verdade , <é um ramo agora. É assim que passamos de baixo para . Enquanto o valor atual em C é positivo, o IP faz uma curva à direita (para executar o loop). Quando atingirmos o zero, ele vire à esquerda.n-11

Vamos dar uma olhada no loop "corpo". Os |espelhos são simples, >e <também são usados ​​como espelhos novamente. Isso significa que o corpo real do loop se resume a

}=)&}=*}=

}move o MP para a borda B , =inverte sua direção para enfrentar o vértice ABC . )incrementa o valor: isso é relevante apenas para a primeira iteração, onde o valor de B ainda é zero: queremos garantir que seja positivo, de modo que a próxima instrução &copie o vizinho certo , ou seja , A , ou seja, o valor atual do fatorial computação, em B .

}depois move o MP para A , =inverte-o novamente para enfrentar o vértice comum. *multiplica dois vizinhos, isto é, as bordas B e C e armazena o resultado em uma . Finalmente, temos outro }=para retornar a C , ainda de frente para o vértice ABC .

Eu espero que você pode ver como isso calcula o fatorial de n-1em Um .

Então, agora que fizemos isso, o contador de loop em C é zero. Queremos colocar o fatorial ao quadrado e depois pegar o módulo com a entrada. É isso que esse código faz:

&}=*{&'%!@

Uma vez que C é zero, &copia o vizinho esquerdo, isto é, o factorial em um . }=*move-se para B e armazena o produto das duas cópias do fatorial (isto é, o quadrado) em B . {volta para C , mas não reverte o MP. Sabemos que o valor da corrente é agora positiva, de modo que &a entrada de cópias de D em C . 'o MP para trás para a direita, ou seja, para um . Recorde, o quadrado da fatorial é em B e a entrada está em C . Então %calcula (n-1)!^2 % nexatamente o que estamos procurando.!imprime o resultado como um número inteiro (0 ou 1) e @finaliza o programa.

Ok, mas essa era a versão não destruída. E a versão do golfe? Você precisa saber mais duas coisas sobre o Hexagony:

  1. As bordas se enrolam. Se o IP atingir uma borda do hexágono, ele pula para a borda oposta. Isso é ambíguo quando o IP atinge um canto diretamente, portanto, atingi-lo também atua como uma ramificação: se o valor atual for positivo, o IP saltará para a borda da grade à sua direita, caso contrário, para a esquerda.
  2. Na verdade, existem 6 IPs. Cada um deles começa em um canto diferente, movendo-se ao longo da borda no sentido horário. Apenas um deles está ativo por vez, o que significa que você pode simplesmente ignorar os outros 5 IPs se não os desejar. Você pode alternar para o próximo IP (em sentido horário) com ]e para o anterior com [. (Você também pode escolher um específico #, mas isso é para outra hora.)

Há também alguns novos comandos nele: \e /são espelhos como |, e ~multiplica o valor atual -1.

Então, como a versão não-golfada se traduz na versão golfada? O código de configuração linear )}?}=&{e a estrutura básica do loop podem ser encontrados aqui:

        ) } ? } .  ->
       . . . . . .
      . . . . . . .
     . . . . . . . .
->  . = & { . < . . .
     . . . . . > ( <
      . . . . . . .
       . . . . . .
        . . . . .

Agora, o corpo do loop cruza as bordas algumas vezes, mas o mais importante é que o cálculo real é transferido para o IP anterior (que começa no canto esquerdo, movendo-se para nordeste):

        ) . . . .
       = . . . ] .
      } = . . } . .
     ~ . / . * . . .
    . . . . . . . . .
     . . . = . > ( <
      . . } . = . .
       . & . \ [ .
        . . . . .

Depois de saltar da ramificação em direção ao sudeste, o IP passa pela borda até os dois =no canto superior esquerdo (que, juntos, não são opcionais), depois ricocheteia na /. O ~inverte o sinal do valor atual, que é importante para as iterações subseqüentes. O IP envolve a mesma borda novamente e finalmente atinge o ponto em [que o controle é entregue ao outro IP.

Agora, este executa o ~}=)&}=*}que desfaz a negação e depois executa o corpo do loop não destruído (menos o =). Finalmente, atinge as ]mãos que controlam de volta ao IP original. (Observe que da próxima vez que executarmos esse IP, ele começará de onde parou e, portanto, chegará à esquina. Precisamos que o valor atual seja negativo para que o IP volte para a borda noroeste em vez do sudeste.)

Depois que o IP original retoma o controle, ele ricocheteia \, executa o restante =e, em seguida, pressiona >para alimentar a próxima iteração do loop.

Agora a parte realmente louca: o que acontece quando o loop termina?

        ) . . . .
       . ( . . ] =
      . . ' . } . }
     . . . % * . . &
    . . . . . . . . .
     . . . = | . . <
      . . } ! . . .
       . & @ . . .
        . . . . .

O IP se move para o nordeste a partir do <e passa para a diagonal nordeste. Portanto, ele termina no mesmo caminho de execução que o corpo do loop ( &}=*}]). O que é realmente muito legal, porque esse é exatamente o código que queremos executar neste momento, pelo menos se adicionarmos outro =}(porque }=}é equivalente a {). Mas como isso não entra no loop anterior novamente? Porque ]muda para o próximo IP, que agora é o IP (até agora não utilizado), que começa no canto superior direito, movendo-se para o sudoeste. A partir daí, o IP continua ao longo da borda, passa para o canto superior esquerdo, desce a diagonal, ricocheteia |e termina @ao executar o bit final do código linear:

=}&)('%!@

(É )(claro que não é possível - eu tive que adicionar o (porque )já estava lá.)

Ufa ... que bagunça ...

Martin Ender
fonte
Agradável! Quão nova é essa? Além disso, você pode querer criar uma página esolangs sempre que você começa uma versão estável
mbomb007
18
@ mbomb007 Eu implementei o idioma há dois dias (e o projetei dois ou três dias antes). E sim, definitivamente adicionarei uma página esolangs, mas acho que a especificação ainda não está 100% estável (ainda existem 3 comandos não atribuídos, por exemplo). Quando sentir que é mais estável, vou adicioná-lo ao esolangs e ao nosso meta post.
Martin Ender
Sob o hexágono expandido, ele1 está no canto mais à esquerda (o ) . Do que 1você está falando aí?
Mbomb007
@ mbomb007 corrigido. O )costumava ser um 1.
Martin Ender
5
+1 apenas para o nível de detalhe na sua explicação de como funciona. Se mais idiomas viessem com um exemplo que detalhasse mais pessoas poderiam usá-los: D
jdarling
66

Pitão, 4 bytes

}QPQ

Imprime Trueou False.

orlp
fonte
12
Eu sei que isso é antigo, mas agora você também pode fazer assim: P_Q e salvar 1 byte.
drobilc
14
É agora possível comP_
Azul
3
@drobilc Você pode cortar o Q, como um EOF quando a função está esperando um argumento, ele usa a entrada
Stan Strum
55

Retina , 16 bytes

^(?!(..+)\1+$)..

Experimente online!

Vamos começar com um clássico: detectar números primos com uma expressão regular . A entrada deve ser dada em unário , usando qualquer caractere imprimível repetido. O conjunto de testes inclui uma conversão de decimal em unário por conveniência.

Um programa Retina que consiste em uma única linha trata essa linha como um regex e imprime o número de correspondências encontradas na entrada, que será 0para números compostos e 1primos.

O lookahead garante que a entrada não seja composta: o backtracking tentará todas as subseqüências possíveis (de pelo menos 2 caracteres) (..+), o lookahead tenta corresponder ao restante da entrada repetindo o que foi capturado aqui. Se isso for possível, isso significa que a entrada tem um divisor maior que 1, mas que é menor que ele próprio. Se for esse o caso, o indicador negativo causa uma falha na correspondência. Para primos, não existe essa possibilidade, e a partida continua.

O único problema é que esse lookahead também aceita 1, então descartamos isso combinando pelo menos dois caracteres com ...

Martin Ender
fonte
Na verdade, é uma expressão irregular, pois os primos não formam uma linguagem regular.
PyRulez
@PyRulez A maioria dos sabores de expressões regulares do mundo real é muito mais poderosa que o conceito teórico de expressões regulares. Eu melhorei a redação embora.
Martin Ender
11
Os mais potentes mecanismos "regex" em campo aberto agora têm poder de reconhecimento igual ao de um autômato linear. Regex de emissão padrão, recursão de padrão, aparência ilimitada e aparência ilimitada são tudo o que você precisa para a análise sensível ao contexto (embora as referências anteriores e essas geralmente ajudem a complicar a análise eficiente), e algumas possuem todas. Nem me inicie nos mecanismos que permitem incorporar código no regex.
eaglgenes101
52

CJam, 4 bytes

qimp

O CJam possui um operador interno para testes de primalidade.

Peter Taylor
fonte
18
Como alternativa:limp
Sp3000
43
pimpmeu cjam.
flawr
12
pimpé objectivamente mais cafetão
MickLH
11
Você também pode fazerl~mp
Vacas grasnam
12
@Cyoce, qlê uma linha de entrada, ianalisa-a como um número inteiro e mpé o interno . CJam tem dois grupos de dois de char built-ins: os "estendidas" começar ee os "matemáticos" começarm
Peter Taylor
48

HTML + CSS, 254 + n máx * 28 bytes

Podemos verificar a primalidade usando expressões regulares. O Mozilla possui @document, que é definido como:

@document [ <url> | url-prefix(<string>) | domain(<string>) | regexp(<string>) ]# {
  <group-rule-body>
}

Para filtrar elementos via CSS com base no URL atual. Como é um passe único, precisamos executar duas etapas:

  1. Obtenha informações do usuário. Esta entrada deve de alguma forma ser refletida no URL atual.
  2. Responda ao usuário com o menor código possível.

1. Obtendo Entrada

A maneira mais curta que consigo descobrir para obter informações e transferi-las para o URL é um GETformulário com caixas de seleção. Para a regex, precisamos apenas de uma sequência única para contar as aparências.

Então começamos com isso (61 bytes):

<div id=q><p id=r>1<p id=s>0</div><form method=GET action=#q>

Temos dois <p>s exclusivos para indicar se o número digitado é primo (1) ou não (0). Também definimos o formulário e sua ação.

Seguido por n max caixas de seleção com o mesmo nome (n max * 28 bytes):

<input type=checkbox name=i>

Seguido pelo elemento de envio (34 bytes):

<input name=d value=d type=submit>

2. Resposta da Tela

Precisamos do CSS (159 bytes) para selecionar a <p>exibição (1 ou 0):

#q,#s,#q:target{display:none}#q:target{display:block}@-moz-document regexp(".*\\?((i=on&)?|(((i=on&)(i=on&)+?)\\4+))d=d#q$"){#s{display:block}#r{display:none}}

»Experimente no codepen.io (apenas no Firefox)

mınxomaτ
fonte
12
+1: Este é o meu abuso favorito de HTML de todos os tempos e o tipo de coisa que me faz amar o codegolf.
cat
Isso é certamente interessante, mas não tenho certeza se satisfaz as regras desse desafio. Em particular, não acho que seja compatível com o seu algoritmo [...] deveria, em teoria, funcionar para números inteiros arbitrariamente grandes. Você não poderia usar uma regex no valor de um campo de entrada também?
Dennis
@Dennis Talvez. Provavelmente até. Mas isso não resolveria o problema que você mencionou. Deixo aqui como uma entrada não concorrente, porque esse é o desafio mais importante para isso.
mınxomaτ 29/12/2015
Por que não? Se você tiver um número unário em um campo de entrada, seu código não dependerá mais do número máximo.
Dennis
5
Hum, pensei um pouco mais sobre isso, e realmente não há diferença entre ter apenas x caixas de seleção e um intérprete que tenha apenas números de bits y. Desconsidere meu comentário anterior.
Dennis
45

Ajuda, WarDoq! , 1 byte

P

Emite 1 se a entrada for prime, 0 caso contrário.

orlp
fonte
40

Hexagonia , 28 bytes

Como Etoplay absolutamente me criticou nessa questão , senti que tinha que superar sua única outra resposta .

?\.">"!*+{&'=<\%(><.*.'(@>'/

Experimente online!

Eu uso o Teorema de Wilson, como Martin fez em sua resposta : Dado n, eu produzo(n-1!)² mod n

Aqui o programa se desenrolou:

   ? \ . "
  > " ! * +
 { & ' = < \
% ( > < . * .
 ' ( @ > ' /
  . . . . .
   . . . .

E aqui está a versão legível :

Muito legível

Explicação:

O programa possui três etapas principais: Inicialização , Fatorial e Produto .

O modelo de memória do Hexagony é uma grade hexagonal infinita. Estou usando 5 locais de memória, conforme mostrado neste diagrama:

Memória

Vou me referir a esses locais (e aos Inteiros armazenados neles) por seus rótulos nesse diagrama.

Inicialização:

Inicialização

O ponteiro de instrução ( IP ) começa no canto superior esquerdo, indo para leste. O ponteiro de memória ( MP ) começa em IN .

Primeiro, ?lê o número da entrada e o armazena em IN . O IP permanece no caminho azul, refletido por \. A sequência "&(move o MP de volta e para a esquerda (para A ), copia o valor de IN para A e o diminui.

O IP sai de um lado do hexágono e entra novamente no outro lado (no caminho verde). Ele executa '+o que move a MP para B e copia o que estava em A . <redireciona o IP para o oeste.

Fatorial:

Eu calculo o fatorial de uma maneira específica, de modo que o quadrado seja fácil. Eu guardo n-1!em B e C da seguinte maneira.

Fatorial

O ponteiro de instruções começa no caminho azul, na direção leste.

='inverte o sentido da MP e move-o para trás para C . Isso é equivalente a, {=mas ter o =local em que foi útil mais tarde.

&{copia o valor de A a C , em seguida, move-se o PM de volta para um . O IP segue o caminho verde, sem fazer nada, antes de alcançar o caminho vermelho, atingindo \e indo para o caminho laranja.

Com (>, decrementamos A e redirecionamos o IP Leste. Aqui ela atinge um ramo: <. Para A positivo , continuamos ao longo do caminho laranja. Caso contrário, o IP será direcionado para o nordeste.

'*move o MP para B e armazena Um * C em B . Aqui é (n-1)*(n-2)onde estava a entrada inicial n. O IP entra novamente no loop inicial e continua diminuindo e se multiplicando até que A atinja 0. (computação n-1!)

Nota : Nos loops seguintes, &armazena o valor de B em C , pois C tem um valor positivo armazenado nele agora. Isso é crucial para calcular o fatorial.

Resultado:

Resultado

Quando A chegar 0. A ramificação direciona o IP ao longo do caminho azul.

=*inverte o MP e armazena o valor de B * C em uma . Então o IP sai do hexágono e entra novamente no caminho verde; executando "%. Isso move o MP para OUT e calcula A mod IN , ou (n-1!)² mod n.

O seguinte {"funciona como não operacional, pois eles se cancelam. !imprime a saída final e *+'(sejam executadas antes da terminação: @.

Após a execução, (com uma entrada de 5) a memória fica assim:

Memória2

As belas imagens do fluxo de controle foram feitas usando o Hexagony Coloror de Timwi .

Obrigado a Martin Ender por gerar todas as imagens, pois não consegui fazê-lo no meu PC.

H.PWiz
fonte
O que você está usando para esses diagramas de memória? Eu vi IDE Esotérico mas eu não poderia começar a correr ...
NieDzejkob
@NieDzejkob, é melhor perguntar a Martin no bate-papo, já que ele fez para mim de qualquer maneira.
H.PWiz
@NieDzejkob Sim, o diagrama de memória pode ser exportado do EsoIDE. chat.stackexchange.com/rooms/27364/… se você quiser conversar um pouco mais sobre isso.
Martin Ender
34

Mornington Crescent , 2448 bytes

Estamos de volta a Londres!

Take Northern Line to Bank
Take Circle Line to Bank
Take District Line to Parsons Green
Take District Line to Bank
Take Circle Line to Hammersmith
Take District Line to Upney
Take District Line to Hammersmith
Take Circle Line to Victoria
Take Victoria Line to Seven Sisters
Take Victoria Line to Victoria
Take Circle Line to Victoria
Take Circle Line to Bank
Take Circle Line to Hammersmith
Take Circle Line to Cannon Street
Take Circle Line to Hammersmith
Take Circle Line to Cannon Street
Take Circle Line to Bank
Take Circle Line to Hammersmith
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Aldgate
Take Circle Line to Hammersmith
Take District Line to Upminster
Take District Line to Hammersmith
Take Circle Line to Notting Hill Gate
Take Circle Line to Hammersmith
Take Circle Line to Notting Hill Gate
Take District Line to Upminster
Take District Line to Bank
Take Circle Line to Victoria
Take Circle Line to Temple
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Pinner
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Pinner
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Pinner
Take Metropolitan Line to Aldgate
Take Circle Line to Hammersmith
Take District Line to Upminster
Take District Line to Victoria
Take Circle Line to Aldgate
Take Circle Line to Victoria
Take Circle Line to Victoria
Take District Line to Upminster
Take District Line to Embankment
Take Circle Line to Embankment
Take Northern Line to Angel
Take Northern Line to Moorgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Aldgate
Take Circle Line to Aldgate
Take Circle Line to Cannon Street
Take District Line to Upney
Take District Line to Cannon Street
Take District Line to Acton Town
Take District Line to Acton Town
Take Piccadilly Line to Russell Square
Take Piccadilly Line to Hammersmith
Take Piccadilly Line to Russell Square
Take Piccadilly Line to Ruislip
Take Piccadilly Line to Ruislip
Take Metropolitan Line to Preston Road
Take Metropolitan Line to Aldgate
Take Circle Line to Aldgate
Take Circle Line to Cannon Street
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Preston Road
Take Metropolitan Line to Moorgate
Take Circle Line to Moorgate
Take Northern Line to Mornington Crescent

A Timwi foi muito gentil ao implementar as estações de fluxo de controle Templee Angelno IDE esotérico , além de adicionar entrada e análise de números inteiros à especificação da linguagem.

Provavelmente, este é um golfe melhor do que o "Olá, Mundo!", Porque desta vez escrevi um script CJam para me ajudar a encontrar o caminho mais curto entre as duas estações. Se você quiser usá-lo (embora eu não saiba por que alguém iria querer ...), você pode usar o intérprete online . Cole este código:

"Mornington Crescent"
"Cannon Street"
]qN/{'[/0=,}$:Q;{Q{1$#!}=\;_oNo'[/1>{']/0="[]"\*}%}%:R;NoQ{R\f{f{\#)}:+}:*},N*

Aqui as duas primeiras linhas são as estações que você deseja verificar. Além disso, cole o conteúdo desta pasta na janela de entrada.

A saída mostrará quais linhas estão disponíveis nas duas estações e, em seguida, uma lista de todas as estações que conectam as duas, classificadas pelo comprimento dos nomes das estações. Ele mostra todos eles, porque às vezes é melhor usar um nome mais longo, porque permite uma linha mais curta ou porque a estação é especial (como Banco ou Templo) para que você queira evitá-lo. Existem alguns casos extremos em que duas estações não estão conectadas por nenhuma outra estação (principalmente, as linhas Metropolitan e District nunca se cruzam); nesse caso, você terá que descobrir outra coisa. ;)

Quanto ao código de MC real, ele se baseia na abordagem fatorial ao quadrado, como muitas outras respostas, porque a MC possui multiplicação, divisão e módulo. Além disso, achei que um único loop seria conveniente.

Uma questão é que os loops são do tipo while, e o decrementar e o incremento são caros, por isso não posso calcular facilmente (n-1)!(para n > 0). Em vez disso, estou computando n!e depois divido nno final. Tenho certeza de que existe uma solução melhor para isso.

Quando comecei a escrever isso, imaginei que armazenar -1em Hammersmith seria uma boa idéia para que eu pudesse diminuir mais barato, mas no final isso pode custar mais do que economizou. Se eu tiver paciência para refazer isso, talvez tente ficar -1em Upminster para poder usar o Hammersmith para algo mais útil.

Martin Ender
fonte
10
Londres está concluída?
Rohan Jhunjhunwala
11
@RohanJhunjhunwala provavelmente
Martin Ender
Uau! Adoro ver perguntas bem pensadas. Eu adoro ver perguntas em que você precisa escrever um programa para escrever um programa.
Rohan Jhunjhunwala
27

Braquilog (V2), 1 byte

ṗ

Experimente online!

Braquilog (V1), 2 bytes

#p

Isso usa o predicado interno #p - Prime, que restringe sua entrada a ser um número primo.

Brachylog é minha tentativa de criar uma versão do Prolog da Code Golf, que é uma linguagem declarativa de código de golfe que usa backtracking e unificação.

Solução alternativa sem built-in: 14 bytes

ybbrb'(e:?r%0)

Aqui está um detalhamento do código acima:

y            The list [0, …, Input]
bbrb         The list [2, …, Input - 1]
'(           True if what's in the parentheses cannot be proven; else false
     e           Take an element from the list [2, …, Input - 1]
     :?r%0       The remainder of the division of the Input but that element is 0
)
Fatalizar
fonte
11
Você também pode editar a versão Brachylog 2 disso na postagem, agora que a sintaxe é um byte mais curto.
11
@ ais523 Verdadeiro, pronto.
Fatalize
A resposta do Brachylog 2 pós-data do desafio?
Scott Milner
11
@ScottMilner Sim, mas isso é explicitamente permitido neste desafio: "Ao contrário dos nossos regras habituais, não hesite em usar uma linguagem (ou versão de idioma) mesmo que seja mais recente do que este desafio"
Fatalize
26

Haskell, 49 bytes

Usando o corolário de xnor para o teorema de Wilson :

main=do n<-readLn;print$mod(product[1..n-1]^2)n>0
Lynn
fonte
Não seria mais curto main=interact$\n-> ...?
John Dvorak
2
Contraintuitivamente, não! Considere que você precisaria estar interact...readem algum lugar, o que torna muito mais longo do que apenas readLn. Geralmente, a donotação pode ser mais concisa do que você imagina, especialmente quando a alternativa é uma lambda.
Lynn
24

Labirinto , 29 bytes

1
?
:
}  +{%!@
(:'(
 } {
 :**

Lê um número inteiro de STDIN e sai ((n-1)!)^2 mod n. O teorema de Wilson é bastante útil para esse desafio.

O programa começa no canto superior esquerdo, começando com o 1qual multiplica o topo da pilha por 10 e adiciona 1. Essa é a maneira do Labyrinth de criar grandes números, mas como as pilhas do Labyrinth são preenchidas com zeros, o efeito final é como se apenas pressionei 1.

?depois lê nde STDIN e o :duplica. }muda npara a pilha auxiliar, a ser usada no final do módulo. (depois diminui ne estamos prontos para começar a calcular o fatorial ao quadrado.

Nosso segundo :(duplicado) está em uma junção, e aqui os recursos de fluxo de controle do Labyrinth entram em jogo. Em uma junção após a execução de uma instrução, se o topo da pilha for positivo, viramos à direita, para negativo, à esquerda e para zero, seguimos em frente. Se você tentar virar, mas bater em uma parede, o Labirinto fará com que você vire na outra direção.

Pois n = 1, como o topo da pilha é ndecrementado, ou 0seguimos em frente. Em seguida, atingimos um no-op 'seguido por outro decréscimo (que nos coloca em -1. Como é negativo, vire à esquerda, executando +plus ( -1 + 0 = -1), {para nvoltar da pilha auxiliar para a main e o %módulo ( -1 % 1 = 0). Então nós produzimos com !e terminamos com @.

Pois n > 1, no segundo :, vire à direita. Em seguida, mudamos }nosso contador de loop copiado para a pilha auxiliar, duplicamos :e multiplicamos duas vezes **, antes de mudar o contador de volta {e decrementar (. Se ainda estamos positivos, tentamos virar à direita, mas não podemos, então o Labirinto nos faz virar à esquerda, continuando o ciclo. Caso contrário, o topo da pilha é o nosso contador de loop, que foi reduzido para 0, que +adicionamos ao nosso calculado ((n-1)!)^2. Finalmente, nvoltamos com o {módulo %, a saída !e a finalização @.

Eu disse que 'é um no-op, mas também pode ser usado para depuração. Corra com a -dbandeira para ver o estado da pilha toda vez que ela 'for ultrapassada!

Sp3000
fonte
2
Quadratura do fatorial é um truque :) muito legal
Lynn
@Mauris Thanks! Eu preciso dar crédito onde é devido embora - vi pela primeira vez o truque usado por xnor aqui
SP3000
5
Sim, a primeira resposta do labirinto não escrita por mim! :)
Martin Ender
24

Utilitários Bash + GNU, 16

  • 4 bytes salvos graças a @Dennis

  • 2 bytes salvos graças a @Lekensteyn

factor|awk NF==2

A entrada é uma linha retirada do STDIN. A saída é sequência vazia para falsey e sequência não vazia para verdade. Por exemplo:

$ ./pr.sh <<< 1
$ ./pr.sh <<< 2
2: 2
$ ./pr.sh <<< 3
3: 3
$ ./pr.sh <<< 4
$
Trauma Digital
fonte
2
Legal, aprendeu sobre outro coreutil. Você pode retirar dois caracteres contando o número de campos:factor|awk NF==2
Lekensteyn
@Lekensteyn - graças - por alguma razão eu perdi o seu comentário antes :)
Digital Trauma
Eu ia postar algo parecido, apenas por mais tempo e sem AWK. Bem feito.
David Conrad
21

Java, 126 121 bytes

Eu acho que precisamos de uma resposta Java para o placar ... então aqui está um loop de divisão de teste simples:

class P{public static void main(String[]a){int i=2,n=Short.valueOf(a[0]);for(;i<n;)n=n%i++<1?0:n;System.out.print(n>1);}}

Como de costume em Java, o requisito "programa completo" torna isso muito maior do que seria se fosse uma função, devido principalmente à mainassinatura.

Em forma expandida:

class P{
    public static void main(String[]a){
        int i=2,n=Short.valueOf(a[0]);
        for(;i<n;)
            n=n%i++<1?0:n;
        System.out.print(n>1);
    }
}

Edit: Corrigido e regravado por Peter nos comentários. Obrigado!

Geobits
fonte
Buggy: relata que 1é excelente. Caso contrário, haveria uma economia de 4-char, removendo pe dizendofor(;i<n;)n=n%i++<1?0:n;System.out.print(n>0);
Peter Taylor
2
OTOH class P{public static void main(String[]a){int i=2,n=Short.valueOf(a[0]);for(;i<n;)n=n%i++<1?0:n;System.out.print(n>1);}}works
Peter Taylor
6
alterar a linha 3 para 'long i = 2, n = Long.valueOf (a [0]); `resulta em nenhuma alteração no comprimento, mas em uma faixa mais ampla de entradas válidas.
James K Polk
4
Em vez de .valueOfvocê pode usar new, como em new Short(a[0]), ou new Long(a[0]), que é um pouco mais curto.
ECS
3
Você pode salvar 4 bytes usando uma interface e soltando o publicmodificador.
RamenChef
18

Brain-Flak , 112 108 bytes

({}[()]){((({})())<>){{}<>(({}<(({}[()])()<>)>)<>)<>{({}[()]<({}[()]<({}())>)>{(<()>)}{})}{}{}}}<>{{}}([]{})

Experimente online!

Como funciona

Inicialmente, a primeira pilha conterá um número inteiro positivo n , a segunda pilha estará vazia.

Começamos decrementando n da seguinte maneira.

(
  {}      Pop n.
  [()]    Yield -1.
)       Push n - 1.

n = 1

Se n = 1 for zero, o loop while

{
  ((({})())<>)
  {
    {}<>(({}<(({}[()])()<>)>)<>)<>{({}[()]<({}[()]<({}())>)>{(<()>)}{})}{}{}
  }
}

é ignorado completamente. Finalmente, o código restante é executado.

<>    Switch to the second stack (empty).
{}    Pop one of the infinite zeroes at the bottom.
{<>}  Switch stacks while the top on the active stack is non-zero. Does nothing.
(
  []    Get the length of the active stack (0).
  {}    Pop another zero.
)     Push 0 + 0 = 0.

n> 1

Se n - 1 for diferente de zero, inserimos o loop que n = 1 pula. Não é um loop "real"; o código é executado apenas uma vez. Consegue o seguinte.

{                   While the top of the active stack is non-zero:
  (
    (
      ({})                Pop and push n - 1.
      ()                  Yield 1.
    )                   Push n - 1 + 1 = n.
    <>                  Switch to the second stack. Yields 0.
  )                   Push n + 0 = n.
                      We now have n and k = n - 1 on the first stack, and n on
                      the second one. The setup stage is complete and we start
                      employing trial division to determine n's primality.
  {                   While the top of the second stack is non-zero:
    {}                  Pop n (first run) or the last modulus (subsequent runs),
                        leaving the second stack empty.
    <>                  Switch to the first stack.
    (
      (
        {}                  Pop n from the first stack.
        <
          (
            (
              {}              Pop k (initially n - 1) from the first stack.
              [()]            Yield -1.
            )               Push k - 1 to the first stack.
            ()              Yield 1.
            <>              Switch to the second stack.
          )               Push k - 1 + 1 = k on the second stack.
        >               Yield 0.
      )               Push n + 0 = n on the second stack.
      <>              Switch to the first stack.
    )               Push n on the first stack.
    <>              Switch to the second stack, which contains n and k.
                    The first stack contains n and k - 1, so it is ready for
                    the next iteration.
    {({}[()]<({}[()]<({}())>)>{(<()>)}{})}{}{}  Compute and push n % k.
  }               Stop if n % k = 0.
}               Ditto.

n% k é calculado usando o algoritmo de módulo de 42 bytes da minha resposta do teste de divisibilidade .

Finalmente, interpretamos os resultados para determinar a primalidade de n .

<>    Switch to the first stack, which contains n and k - 1, where k is the
      largest integer that is smaller than n and divides n evenly.
      If (and only if) n > 1 is prime, k = 1 and (thus) k - 1 = 0.
{     While the top of the first stack is non-zero:
  {}    Pop it.
}     This pops n if n is prime, n and k - 1 if n is composite.
(
  []    Yield the height h of the stack. h = 1 iff n is prime).
  {}    Pop 0.
)     Push h + 0 = h.
Dennis
fonte
2
Você não precisa colocar o último 0 na pilha, pois o verdadeiro 1 no topo é suficiente; você pode salvar dois bytes dessa maneira removendo o último {}.
Steven H.
11
Hum, estou rasgado. Por um lado, a pergunta diz que o produto deve consistir apenas de um valor verdadeiro ou falso e 1 0é de dois valores. Por outro lado, aceitamos matrizes desde que a linguagem as considere verdadeiras ou falsas e vários itens de pilha sejam a coisa mais próxima que a Brain-Flak tem das matrizes. Pode valer a pena levar isso para meta.
Dennis #
Eu verifiquei com o criador do Brain-Flak que 1 0é verdade. chat.stackexchange.com/transcript/message/32746241#32746241
Steven H.
3
Relevante meta discussão: Truthiness em Brain-Flak e linguagens baseadas em pilha semelhantes
Dennis
17

R, 37 29 bytes

n=scan();cat(sum(!n%%1:n)==2)

Usa divisão de teste. scan()lê um número inteiro de STDIN e cat()grava em STDOUT.

Geramos um vetor de comprimento que nconsiste nos números inteiros 1 a nmódulo n. Testamos se cada um é 0 negando ( !), que retorna um valor lógico que é verdadeiro quando o número é 0 e falso quando é maior que 0. A soma de um vetor lógico é o número de elementos verdadeiros e, para os números primos, esperamos o único módulo diferente de zero é 1 e n, portanto, esperamos que a soma seja 2.

Economizou 8 bytes graças ao flodel!

Alex A.
fonte
Com f=function(x)sum(!x%%1:x)==2você pode fazê-lo em 28 bytes.
Mutador
2
@ AndréMuta Para esse desafio, todos os envios devem ser programas completos, e não apenas funções. Obrigado pela sugestão embora.
21415 Alex A.
17

TI-BASIC, 12 bytes

2=sum(not(fPart(Ans/randIntNoRep(1,Ans

Bem direto. randIntNoRep(dá uma permutação aleatória de todos os números inteiros de 1 a Ans.

Isso dobra um pouco as regras; porque as listas no TI-BASIC são limitadas a 999 elementos que eu interpretei

suponha que a entrada possa ser armazenada no seu tipo de dados

como significando que todos os tipos de dados podem ser assumidos para acomodar a entrada. O OP concorda com esta interpretação.

UMA solução de 17 bytes que realmente funciona até 10 ^ 12 ou mais:

2=Σ(not(fPart(Ans/A)),A,1,Ans
lirtosiast
fonte
@toothbrush O TI-BASIC é uma linguagem tokenizada ; portanto, cada token aqui é de um byte, exceto randIntNoRep(dois.
lirtosiast 13/09/15
+1 Ah, eu nunca vi o TL-BASIC antes. Obrigado por me deixar saber
Escova de dentes
11
Embora seja um pouco injusto, não é ...? Devo escrever uma linguagem de golfe que exija apenas 1-4 bytes (o ID da pergunta) e, em seguida, os parâmetros. Ele seleciona a resposta principal em um idioma que entende, executa (passando quaisquer parâmetros) e retorna o resultado ... Será que isso está violando as regras? :-)
Toothbrush
@toothbrush Na defesa do TI-BASIC: para o intérprete, não é mais injusto que os comandos de um caractere de Pyth e CJam, e o TI-BASIC é mais legível.
lirtosiast 13/09/15
11
Verdadeiro. Não gosto desses tipos de idiomas, já que as soluções em quase todos os outros idiomas são mais longas ... embora recentemente tenha batido o CJam com o VB6 ! : -]
Escova de dentes
15

PARI / GP, 21 bytes

print(isprime(input))

Funciona para insumos ridiculamente grandes, porque é para isso que o PARI / GP é feito.

Lynn
fonte
6
isprimefaz uma prova de primalidade APR-CL, assim diminui bastante à medida que as entradas ficam muito grandes. ispseudoprime(input)faz um teste de provável provável AES BPSW, que será muito mais rápido por mais de 100 dígitos. Ainda não existem contra-exemplos conhecidos após 35 anos. A versão 2.1 e anterior do Pari, de antes de 2002, usa um método diferente que pode facilmente fornecer resultados falsos, mas ninguém deve usá-lo.
DanaJ
15

TI-BASIC, 24 bytes

Observe que os programas TI-Basic usam um sistema de token; portanto, a contagem de caracteres não retorna o valor real de bytes do programa.

Upvote resposta de Thomas Kwa , é superior.

:Prompt N
:2
:While N≠1 and fPart(N/Ans
:Ans+1
:End
:N=Ans

Amostra:

N=?1009
                         1
N=?17
                         1
N=?1008
                         0
N=?16
                         0

Agora retorna 0se não for um primo, ou 1se for.

Zenohm
fonte
3
A raiz quadrada não é apenas uma otimização que você realmente não precisa para que o programa esteja correto?
Martin Ender
Por que você precisaria dividir por dois?
Geobits
Eu sempre amo respostas TI-BASIC.
Grant Miller
15

Stack Cats , 62 + 4 = 66 bytes

*(>:^]*(*>{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}*<)]*(:)*=<*)>]

Precisa ser executado com os -lnsinalizadores da linha de comando (daí +4 bytes). Imprime 0para números compostos e 1para números primos.

Experimente online!

Acho que este é o primeiro programa não-trivial do Stack Cats.

Explicação

Uma rápida introdução ao Stack Cats:

  • O Stack Cats opera em uma fita infinita de pilhas, com uma cabeça de fita apontando para uma pilha atual. Cada pilha é inicialmente preenchida com uma quantidade infinita de zeros. Geralmente ignorarei esses zeros na minha redação, portanto, quando digo "a parte inferior da pilha", quero dizer o menor valor diferente de zero e se digo "a pilha está vazia", ​​quero dizer que há apenas zeros nela.
  • Antes do programa iniciar, a -1é empurrada para a pilha inicial e, em seguida, toda a entrada é empurrada para cima dela. Nesse caso, devido ao -nsinalizador, a entrada é lida como um número inteiro decimal.
  • No final do programa, a pilha atual é usada para saída. Se houver um -1na parte inferior, ele será ignorado. Mais uma vez, devido à-n sinalizador, os valores da pilha são simplesmente impressos como números inteiros decimais separados por avanço de linha.
  • O Stack Cats é uma linguagem de programa reversível: todo código pode ser desfeito (sem o Stack Cats acompanhar um histórico explícito). Mais especificamente, para reverter qualquer parte do código, você simplesmente o espelha, por exemplo, <<(\-_)torna-se(_-/)>> . Esse objetivo de design impõe restrições bastante severas a quais tipos de operadores e construções de fluxo de controle existem no idioma e que tipos de funções você pode calcular no estado da memória global.

  • Para completar, todo programa Stack Cats precisa ser auto-simétrico. Você pode perceber que esse não é o caso do código fonte acima. É para isso que serve a -lbandeira: espelha implicitamente o código à esquerda, usando o primeiro caractere para o centro. Portanto, o programa real é:

    [<(*>=*(:)*[(>*{[[>[:<[>>_(_-<<(-!>)>(>-)):]<^:>!->}<*)*[^:<)*(>:^]*(*>{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}*<)]*(:)*=<*)>]

Programar efetivamente com todo o código é altamente não trivial e não intuitivo e ainda não descobriu como um humano pode fazê-lo. Forçamos esse programa brutalmente para tarefas mais simples, mas não conseguimos chegar nem perto disso à mão. Felizmente, encontramos um padrão básico que permite ignorar metade do programa. Embora isso seja certamente subótimo, atualmente é a única maneira conhecida de programar efetivamente no Stack Cats.

Portanto, nesta resposta, o modelo do referido padrão é este (há alguma variabilidade na forma como é executado):

[<(...)*(...)>]

Quando o programa é iniciado, a fita da pilha fica assim (por 4exemplo, para entrada ):

     4    
... -1 ...
     0
     ^

O [move o topo da pilha para a esquerda (e a cabeça da fita) - chamamos isso de "empurrar". E isso <move a cabeça da fita sozinha. Então, após os dois primeiros comandos, temos esta situação:

...   4 -1 ...
    0 0  0
    ^

Agora o (...)é um loop que pode ser usado facilmente como condicional: o loop é inserido e deixado apenas quando a parte superior da pilha atual é positiva. Como atualmente é zero, pulamos a primeira metade inteira do programa. Agora o comando central é *. Isso é simplesmente XOR 1, ou seja, alterna o bit menos significativo do topo da pilha e, nesse caso, transforma o 0em um 1:

... 1 4 -1 ...
    0 0  0
    ^

Agora encontramos a imagem invertida do (...). Desta vez, o topo da pilha é positivo e vamos fazer introduzir o código. Antes de analisarmos o que acontece entre parênteses, deixe-me explicar como encerraremos no final: queremos garantir que, no final deste bloco, tenhamos a cabeça da fita com um valor positivo novamente (para que o loop termina após uma única iteração e é usado simplesmente como uma condicional linear), que a pilha para a direita contém a saída e que o direito de pilha que detém um -1. Se for esse o caso, deixamos o loop, passamos >para o valor de saída e o ]pressionamos para -1que possamos ter uma pilha limpa de saída.

É isso. Agora, dentro dos parênteses, podemos fazer o que quisermos para verificar a primalidade, desde que asseguremos que configuramos as coisas conforme descrito no parágrafo anterior no final (o que pode ser feito facilmente com alguns movimentos de empurrar e mover a cabeça da fita). Tentei primeiro resolver o problema com o teorema de Wilson, mas acabei com mais de 100 bytes, porque a computação fatorial ao quadrado é realmente muito cara no Stack Cats (pelo menos não encontrei um caminho curto). Então, eu fui com a divisão de testes e isso realmente ficou muito mais simples. Vejamos o primeiro bit linear:

>:^]

Você já viu dois desses comandos. Além disso, alterna os :dois principais valores da pilha atual e ^XORs o segundo valor no valor superior. Isso cria :^um padrão comum para duplicar um valor em uma pilha vazia (extraímos um zero por cima do valor e depois o transformamos em zero 0 XOR x = x). Então, depois disso, nossa seção de fita fica assim:

         4    
... 1 4 -1 ...
    0 0  0
         ^

O algoritmo de divisão de teste que eu implementei não funciona para entrada 1, portanto, devemos pular o código nesse caso. Podemos mapear facilmente 1para 0e tudo mais com valores positivos *, então veja como fazemos isso:

*(*...)

Ou seja, nos transformamos 1em 0, pular uma grande parte do código, se conseguirmos de fato 0, mas por dentro nós imediatamente desfazemos o código *para que recuperemos nosso valor de entrada. Só precisamos garantir novamente que terminemos com um valor positivo no final dos parênteses para que eles não comecem a repetir. Dentro do condicional, movemos uma pilha à direita com o >e, em seguida, iniciamos o loop principal da divisão de teste:

{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}

As chaves (em oposição aos parênteses) definem um tipo diferente de loop: é um loop do-while, o que significa que sempre é executado por pelo menos uma iteração. A outra diferença é a condição de terminação: ao entrar no loop, o Stack Cat lembra o valor superior da pilha atual ( 0no nosso caso). O loop será executado até que esse mesmo valor seja visto novamente no final de uma iteração. Isso é conveniente para nós: em cada iteração, simplesmente calculamos o restante do próximo divisor em potencial e o movemos para essa pilha em que estamos iniciando o loop. Quando encontramos um divisor, o restante é 0e o loop para. Vamos tentar os divisores começando em n-1e depois diminuindo-os para 1. Isso significa que a) sabemos que isso terminará quando chegarmos1o mais tardar eb) podemos determinar se o número é primo ou não, inspecionando o último divisor que tentamos (se for 1, é primo, caso contrário, não é).

Vamos lá. Há uma seção linear curta no começo:

<-!<:^>[:

Você sabe o que a maioria dessas coisas faz até agora. Os novos comandos são -e !. O Stack Cats não possui operadores de incremento ou decremento. No entanto, possui -(negação, isto é, multiplique por -1) e !(bit a bit NÃO, ou seja, multiplique por -1e diminua). Eles podem ser combinados em um incremento !-ou decremento -!. Então, diminuímos a cópia nem cima da -1, em seguida, fazemos outra cópia nna pilha à esquerda, buscamos o novo divisor de avaliação e colocamos em baixo n. Então, na primeira iteração, obtemos o seguinte:

      4       
      3       
... 1 4 -1 ...
    0 0  0
      ^

Em iterações adicionais, o 3será substituído pelo próximo divisor de teste e assim por diante (enquanto as duas cópias de nsempre terão o mesmo valor neste momento).

((-<)<(<!-)>>-_)

Este é o cálculo do módulo. Como os loops terminam com valores positivos, a idéia é começar -ne adicionar repetidamente o divisor de teste daté obtermos um valor positivo. Quando o fazemos, subtraímos o resultado de isso nos dá o restante. O mais complicado aqui é que não podemos simplesmente colocar um -nno topo da pilha e iniciar um loop que acrescenta d: se o topo da pilha for negativo, o loop não será inserido. Essas são as limitações de uma linguagem de programação reversível.

Portanto, para contornar esse problema, começamos com o ntopo da pilha, mas o negamos apenas na primeira iteração. Novamente, isso parece mais simples do que parece ser ...

(-<)

Quando o topo da pilha é positivo (ou seja, apenas na primeira iteração), nós o negamos -. No entanto, não podemos fazer isso (-)porque não sairíamos do loop até que -fosse aplicado duas vezes. Então, movemos uma célula para a esquerda <porque sabemos que há um valor positivo lá (o 1). Ok, agora negamos de maneira confiável na primeira iteração. Mas temos um novo problema: a cabeça da fita agora está em uma posição diferente na primeira iteração do que em todas as outras. Precisamos consolidar isso antes de seguirmos em frente. O próximo <move a cabeça da fita para a esquerda. A situação na primeira iteração:

        -4       
         3       
...   1  4 -1 ...
    0 0  0  0
    ^

E na segunda iteração (lembre-se de que adicionamos duma vez ao -nagora):

      -1       
       3       
... 1  4 -1 ...
    0  0  0
    ^

O próximo condicional mescla esses caminhos novamente:

(<!-)

Na primeira iteração, a cabeça da fita aponta para zero, portanto isso é ignorado completamente. Em outras iterações, a cabeça da fita aponta para uma, porém, executamos isso, movemos para a esquerda e incrementamos a célula lá. Como sabemos que a célula começa do zero, agora sempre será positiva para que possamos sair do loop. Isso garante que sempre terminemos com duas pilhas restantes da pilha principal e agora podemos voltar com ela >>. Então, no final do ciclo do módulo, fazemos -_. Você já sabe -. _é subtrair o que ^é XOR: se o topo da pilha estiver ae o valor abaixo bdele for substituído apor b-a. Desde que negamos a, porém, -_substitui apor b+a, adicionandod em nosso total de corrida.

Depois que o loop termina (atingimos um valor positivo), a fita fica assim:

        2       
        3       
... 1 1 4 -1 ...
    0 0 0  0
        ^

O valor mais à esquerda pode ser qualquer número positivo. De fato, é o número de iterações menos uma. Há outro pequeno bit linear agora:

_<<]>:]<]]

Como eu disse anteriormente, precisamos subtrair o resultado de dpara obter o restante real ( 3-2 = 1 = 4 % 3), então fazemos apenas _mais uma vez. Em seguida, precisamos limpar a pilha que temos incrementado à esquerda: quando tentamos o próximo divisor, ele precisa ser zero novamente, para que a primeira iteração funcione. Então, vamos para lá e colocamos esse valor positivo na outra pilha auxiliar <<]e depois voltamos à nossa pilha operacional com outra >. Nós puxar para cima dcom :e empurrá-lo de volta para o -1com ]e depois passamos o restante em nossa pilha condicional com <]]. Esse é o fim do loop de divisão de teste: isso continua até obtermos um zero restante, nesse caso a pilha à esquerda contémnO maior divisor (exceto n).

Depois que o loop termina, há pouco *<antes de juntarmos os caminhos à entrada 1novamente. O *simplesmente transforma o zero em um 1, o que precisaremos daqui a pouco, e depois passaremos para o divisor <(para que estejamos na mesma pilha da entrada 1).

Neste ponto, ajuda a comparar três tipos diferentes de entradas. Primeiro, o caso especial n = 1em que não fizemos nada disso:

         0    
... 1 1 -1 ...
    0 0  0
         ^

Então, nosso exemplo anterior n = 4, um número composto:

    2           
    1    2 1    
... 1 4 -1 1 ...
    0 0  0 0
         ^

E, finalmente, n = 3um número primo:

    3           
    1    1 1    
... 1 3 -1 1 ...
    0 0  0 0
         ^

Portanto, para números primos, temos um 1nesta pilha e, para números compostos, temos um 0ou um número positivo maior que 2. Transformamos essa situação no 0ou 1precisamos com o seguinte trecho de código final:

]*(:)*=<*

]apenas empurra esse valor para a direita. Então *é usado para simplificar bastante a situação condicional: alternando o bit menos significativo, transformamos 1(primo) em 0, 0(composto) no valor positivo 1, e todos os outros valores positivos ainda permanecerão positivos. Agora só precisamos distinguir entre 0e positivo. É aí que usamos outro (:). Se o topo da pilha for 0(e a entrada for primordial), isso será simplesmente ignorado. Mas se o topo da pilha for positivo (e a entrada for um número composto), isso será trocado com o 1, de modo que agora temos o 0composto e1para números primos - apenas dois valores distintos. Claro, eles são o oposto do que queremos produzir, mas isso é facilmente corrigido com outro *.

Agora tudo o que resta é para restaurar o padrão de pilhas esperados por nosso quadro envolvente: Cabeça de fita em um valor positivo, resultar no topo da pilha para a direita, e um único -1na direita pilha de que . É para isso que =<*serve. =troca as partes superiores das duas pilhas adjacentes, movendo assim -1para a direita do resultado, por exemplo, para entrada 4novamente:

    2     0       
    1     3       
... 1 4   1 -1 ...
    0 0 0 0  0
          ^

Então, apenas movemos para a esquerda <e transformamos esse zero em um com *. E é isso.

Se você quiser se aprofundar no funcionamento do programa, use as opções de depuração. Adicione o -dsinalizador e insira "onde quiser ver o estado atual da memória, por exemplo , assim , ou use o -Dsinalizador para obter um rastreamento completo de todo o programa . Como alternativa, você pode usar o EsotericIDE de Timwi, que inclui um interpretador Stack Cats com um depurador passo a passo.

Martin Ender
fonte
3
>:^]deve ser o logotipo oficial da Stack Cats
Alex A.
14

Haskell, 54 bytes

import Data.Numbers.Primes
main=readLn>>=print.isPrime

Não há muito o que explicar.

nimi
fonte
11
A mesma pontuação pode ser alcançada (embora muito ineficientemente) sem bibliotecas externas, usando o teorema de Wilson:main=do n<-readLn;print$n>1&&mod(product[1..n-1]+1)n<1
Lynn
9
Podemos até diminuir: main=do n<-readLn;print$mod(product[1..n-1]^2)n>0é de 49 bytes.
Lynn
4
@Mauris: Legal. Poste-o como uma resposta separada.
nimi
14

Ruby, 15 + 8 = 23 bytes

p$_.to_i.prime?

Exemplo de execução:

bash-4.3$ ruby -rprime -ne 'p$_.to_i.prime?' <<< 2015
false
homem a trabalhar
fonte
Heheh, eu sabia que haveria um embutido em Ruby em algum lugar, mas não me incomodava em procurá-lo, então respondi em C. +1.
Level River St
@steveverrill, eu sabia porque era uma grande ajuda para o Projeto Euler.
manatwork
14

JavaScript, 39 36 bytes

Economizou 3 bytes graças ao ETHproductions:

for(i=n=prompt();n%--i;);alert(1==i)

Exibe true para um prime, false caso contrário.

O loop for testa todos os números i de n-1 até que i seja um divisor. Se o primeiro divisor encontrado for 1 , é um número primo.

Solução anterior (39 bytes):

for(i=n=prompt();n%--i&&i;);alert(1==i)

Como foi deixado um teste desnecessário:

for(i=2,n=prompt();n%i>0&&i*i<n;i++);alert(n%i>0) //49: Simple implementation: loop from 2 to sqrt(n) to test the modulo.
for(i=2,n=prompt();n%i>0&&i<n;i++);alert(n==i)    //46: Replace i*i<n by i<n (loop from 2 to n) and replace n%i>0 by n==i
for(i=2,n=prompt();n%i&&i<n;i++);alert(n==i)      //44: Replace n%i>0 by n%i
for(i=2,n=prompt();n%i&&i++<n;);alert(n==i)       //43: Shorten loop increment
for(i=n=prompt();n%--i&&i>0;);alert(1==i)         //41: Loop from n to 1. Better variable initialization.
for(i=n=prompt();n%--i&&i;);alert(1==i)           //39: \o/ Replace i>0 by i

Postei apenas a solução de 39 bytes porque a melhor resposta JavaScript já era de 40 bytes.

Hedi
fonte
2
Bem-vindo à programação de quebra-cabeças e código de golfe!
Dennis
2
Ótima resposta! O programa &&inão faz nada neste programa, portanto você pode removê-lo.
ETHproductions
deve adicionar n>1à condição final, se você não quiser 1ser primo.
Titus
11
@Titus Se a entrada for 1o loop for fará n%--iuma vez: 1%0retorna NaNe para o loop. Quando alerté chamado ijá é igual a 0so 1==iretorna false.
Hedi
2
i <2 (e algum texto) #
Scheintod 16/03/18
13

Caracóis, 122

A entrada deve ser dada em unário. Os dígitos podem ter qualquer mistura de caracteres, exceto novas linhas.

^
..~|!(.2+~).!~!{{t.l=.r=.}+!{t.!.!~!{{r!~u~`+(d!~!.r~)+d~,.r.=.(l!~u~)+(d!~l~)+d~,.l.},l=(.!.)(r!~u~)+(d!~!.r~)+d~,.r.!.

Nesta linguagem de correspondência de padrões 2D, o estado do programa consiste apenas na localização atual da grade, no conjunto de células que foram correspondidas e na posição no código do padrão. Também é ilegal viajar para um quadrado correspondente. É complicado, mas é possível armazenar e recuperar informações. A restrição de viajar para uma célula correspondente pode ser superada com retorno, teleporte ( t) e afirmações ( =, !) que deixam a grade sem modificação após a conclusão.

Fatoração de 25

A fatoração para um número composto ímpar começa marcando um conjunto de células mutuamente não adjacentes (azul no diagrama). Em seguida, a partir de cada célula amarela, o programa verifica se há um número igual de células não azuis em ambos os lados da célula azul adjacente, alternando entre os dois lados. O diagrama mostra esse padrão para uma das quatro células amarelas que devem ser verificadas.

Código anotado:

^                         Match only at the first character
..~ |                     Special case to return true for n=2
!(.2 + ~)                 Fail for even numbers
. !~                      Match 1st character and fail for n=1
!{                        If the bracketed pattern matches, it's composite.
  (t. l=. r=. =(.,~) )+   Teleport to 1 or more chars and match them (blue in graphic)
                          Only teleport to ones that have an unmatched char on each side.
                          The =(.,~) is removed in the golfed code. It forces the
                          teleports to proceed from left to right, reducing the
                          time from factorial to exponential.
  !{                      If bracketed pattern matches, factorization has failed.
    t . !. !~             Teleport to a square to the left of a blue square (yellow in diagram)
    !{                    Bracketed pattern verifies equal number of spaces to
                          the left or right of a blue square.
      {              
        (r!~ u~)+         Up...
        (d!~!. r~)+       Right...
        d~,               Down...
        . r . =.          Move 1 to the right, and check that we are not on the edge;
                          otherwise d~, can fall off next iteration and create and infinite loop
        (l!~ u~)+         Up...
        (d!~ l~)+         Left...
        d ~,              Down...
        . l .             Left 1
      } ,                 Repeat 0 or more times
      l  =(. !.)          Check for exactly 1 unused char to the left
      (r!~ u~)+           Up...
      (d!~!. r~)+         Right...
      d ~,                Down...
      . r . !.
    }
  }
}
feersum
fonte
13

C, 67 bytes

i,n;main(p){for(scanf("%d",&i),n=i;--i;p=p*i*i%n);putchar(48+p%n);}

Imprime !1(um valor falsey, pela definição de Peter Taylor ) , 0se (n-1)!^2 == 0 (mod n)e de 1outra forma.

EDIT : Depois de alguma discussão no chat, puts("!1"+p%n)parece ser um pouco barato, então eu o substituí. O resultado é um byte a mais.

EDIT : Corrigido para grandes entradas.

Soluções mais curtas

56 bytes : Conforme recomendado nos comentários de pawel.boczarski, eu poderia receber informações unárias lendo o número de argumentos da linha de comando:

p=1,n;main(i){for(n=--i;--i;p=p*i*i%n);putchar(48+p%n);}

invocando o programa como

$ ./a.out 1 1 1 1 1
1                        <-- as 5 is prime

51 bytes : se você permitir "output" por meio de códigos de retorno:

p=1,n;main(i){for(n=--i;--i;p=p*i*i%n);return p%n;}
Lynn
fonte
Sua solução pode ser reduzida usando a representação unária (número de argumentos da linha de comando), como na minha solução postada. Você pode cortar alguns bytes na chamada scanf.
pawel.boczarski
puts("!1"+p%n)Como você poderia fazer a+bpelos char*valores?
Erik the Outgolfer
Se a sequência "!1"começar no endereço a, a+1você encontrará a sequência "1".
21416 Lynn
@Lynn Oh, eu pensei que era para concatenação (sim, melhor deixar que a strcat(const char*,const char*).)
Erik o Outgolfer
Você poderia mudar p=p*i*i%nparap*=i*i%n
Albert Renshaw
12

Python 3, 59 bytes

Agora usa em input()vez de argumentos de linha de comando. Graças a @Beta Decay

n=int(input())
print([i for i in range(1,n)if n%i==0]==[1])
uno20001
fonte
Receber entrada usando input()seria muito menor
Beta Decay
Obrigado, eu já escrevi com o uso de input (), mas esqueci de atualizar minha resposta. Obrigado novamente!
uno20001
4
52 bytes: n=m=int(input()),print(all(n%m for m in range(2,n)))
John Lyon
11
Você está falando sério. Gaste 25 caracteres extras para uma aceleração quadrática esfarrapada? Aqui nós odiamos bytes . Passamos cada hora, minuto e segundo de nossas vidas nos livrando do décimo nono byte. (Brincadeirinha Mas nós não fazemos otimizações tempo que aumentam a duração do programa..)
CalculatorFeline
2
Use em n%i<1vez disso.
Erik the Outgolfer
12

APL, 40 13 bytes

2=+/0=x|⍨⍳x←⎕

Divisão de prova com o mesmo algoritmo que minha resposta R . Nós atribuímos xà entrada de STDIN ( ⎕) e obtemos o restante para xdividido por cada número inteiro de 1 a x. Cada restante é comparado com 0, o que nos dá um vetor de uns e zeros indicando quais números inteiros se dividem x. Isso é somado usando +/para obter o número de divisores. Se esse número for exatamente 2, isso significa que os únicos divisores são 1 e x, portanto, xé primo.

Alex A.
fonte
12

Python 2, 44

P=n=1
exec"P*=n*n;n+=1;"*~-input()
print P%n

Como a resposta Python do Sp3000 , mas evita armazenar a entrada contando a variável nde1 o valor de entrada.

xnor
fonte
12

Metaprogramação de modelos C ++. 166 131 119 bytes.

O código é compilado se a constante for primária e não será compilado se composto ou 1.

template<int a,int b=a>struct t{enum{x=t<a,~-b>::x+!(a%b)};};
template<int b>struct t<b,0>{enum{x};};
int _[t<1>::x==2];

(todas as novas linhas, exceto a final, são eliminadas na versão "real").

Eu acho que "falha na compilação" é um valor de retorno falsey para uma linguagem de metaprogramação. Observe que ele não vincula (por isso, se você o alimentar como primo, obterá erros de vinculação) como um programa C ++ completo.

O valor a testar é o número inteiro na última "linha".

exemplo ao vivo .

Yakk
fonte