Esses meus primos são sempre linhas sólidas

12

Vamos criar uma grade N × N de espaços e sublinhados que podem ser usados ​​para determinar visualmente se um número é primo. (N pode ser qualquer número inteiro positivo.)

Essa grade possui três regras simples:

  1. A enésima coluna contém o padrão repetido de n - 1 sublinhados seguido por um espaço. Esse padrão inicia na primeira linha e é interrompido, possivelmente no meio do padrão, na linha N. (Linhas e colunas são indexadas 1).
  2. A primeira coluna é substituída por todos os sublinhados em vez de todos os espaços.
  3. Se ocorrer um espaço em algum lugar, o índice da linha é igual ao índice da coluna, sendo substituído por um sublinhado.

Exemplo: N = 10

           1
  1234567890 <-- column indices
 1__________
 2__________
 3__________
 4_ ________
 5__________
 6_  _______
 7__________
 8_ _ ______
 9__ _______
10_ __ _____
 ^ row indices

Os índices são apenas para maior clareza. A grade simples (o que seu programa deve gerar) é:

__________
__________
__________
_ ________
__________
_  _______
__________
_ _ ______
__ _______
_ __ _____

Notar que:

  • A primeira coluna é todos os sublinhados.
  • A segunda coluna coloca espaço sublinhado, espaço sublinhado, etc., exceto o sublinhado na linha 2.
  • A terceira coluna apresenta sublinhado, espaço sublinhado, espaço sublinhado, etc., exceto o sublinhado na linha 3.
  • etc.

Observe também que, além de 1, apenas as linhas com números primos têm sublinhados em todas as colunas.

Como os sublinhados abrangem toda a largura da fonte, cada linha numerada principal forma uma linha contínua e sólida. Portanto, verificar se um número é primo ou não é bastante fácil visualmente; basta verificar se sua linha é sólida em todas as colunas. (De fato, basta olhar para a raiz quadrada do índice de linha, mas produzir essa grade parece menos elegante.)

Programa

Escreva um programa que desenhe essas grades dadas N via stdin (ou alternativa mais próxima). A saída vai para stdout (ou alternativa mais próxima) e deve conter apenas espaços, sublinhados e novas linhas, com uma nova linha à direita opcional.

O código mais curto vence.

code-golf primes
fonte
Eu não entendo como ele determina o número primo
Filip Bartuzi
5
@FilipBartuzi Talvez vá para en.wikipedia.org/wiki/Sieve_of_Eratosthenes
"A enésima coluna contém o padrão repetido de n - 1 sublinhados seguido por um espaço." Portanto, a coluna n = 1 não deve ter todos os espaços, nem todos os sublinhados?
algorithmshark
6
Devo dizer que não gosto particularmente do requisito "sem nova linha final". Isso é muito difícil em alguns idiomas, totalmente impossível em outros e afeta apenas os programas impressos em STDOUT.
Dennis
4
A descrição foi difícil para mim entender. É assim que eu descreveria: Comece com uma grade de N linhas de N sublinhados. Para a nlinha th, torne o kth caractere um espaço se kfor um divisor mque não seja 1 ou m.
Casey Chu

Respostas:

7

CJam, 33 28 27 bytes

q~,:)_f{f{md\1=+'_S?}0'_tN}

Experimente online.

Como funciona

q~        " Read one line from STDIN and evaluate it.                                     ";
,:)       " For “N”, push [ 1 ... N ].                                                    ";
_         " Push a copy.                                                                  ";
f{        " For each “I in [ 1 ... N ], push “I   [ 1 ... N ]”; then:                     ";
  f{      " For each “J in [ 1 ... N ], push “J   I”; then:                               ";
    md\   " Push “J % I   J / I”.                                                         ";
    1=+   " Calculate “J % I + (J / I == 1)”.                                             ";
    '_S?  " Push an underscore if the result is truthy and a space otherwise.             ";
  }       "                                                                               ";
  0'_t    " Replace the first character of the resulting array by an underscore.          ";
  N       " Push a newline.                                                               ";
}         "                                                                               ";

Exemplo de execução

$ cjam solid-primes.cjam <<< 10
__________
__________
__________
_ ________
__________
_  _______
__________
_ _ ______
__ _______
_ __ _____
$ cjam solid-primes.cjam <<< 100 | md5sum # trailing newline
e4396b316989813dada21141b569ccf9  -
Dennis
fonte
Vou postar uma explicação quando terminar o golfe.
Dennis
9
33 bytes e você não terminou o golfe ??
5

Ruby, 77 73 caracteres

puts (1..n=gets.to_i).map{|a|?_+(2..n).map{|b|a!=b&&a%b==0? ' ':?_}.join}

Alguns truques que usei:

  • O ..operador tem quase a menor precedência de todos os operadores no Ruby, portanto, (1..n=gets.to_i)apenas funciona.

  • Em vez de adicionar uma a!=1condição extra ao verificar se o caractere deve ser um espaço em vez de um sublinhado (como a primeira linha é toda sublinhada), iniciei o intervalo 2e acrescentei um extra ?_.

  • A linha A pode se tornar a linha B:

    A | a%b==0&&a!=b ? ' ':?_
B | a!=b&&a%b==0? ' ':?_

    porque eu tenho que ter um espaço extra entre be ?na linha A, mas isso não é necessário entre 0e ?na linha B. b?é um método Ruby válido, mas 0?não é.

  • putsjuntará automaticamente matrizes com novas linhas para você, eliminando a necessidade de um extra *"\n".

Saída para n=100:

____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
_ __________________________________________________________________________________________________
____________________________________________________________________________________________________
_  _________________________________________________________________________________________________
____________________________________________________________________________________________________
_ _ ________________________________________________________________________________________________
__ _________________________________________________________________________________________________
_ __ _______________________________________________________________________________________________
____________________________________________________________________________________________________
_   _ ______________________________________________________________________________________________
____________________________________________________________________________________________________
_ ____ _____________________________________________________________________________________________
__ _ _______________________________________________________________________________________________
_ _ ___ ____________________________________________________________________________________________
____________________________________________________________________________________________________
_  __ __ ___________________________________________________________________________________________
____________________________________________________________________________________________________
_ _  ____ __________________________________________________________________________________________
__ ___ _____________________________________________________________________________________________
_ ________ _________________________________________________________________________________________
____________________________________________________________________________________________________
_   _ _ ___ ________________________________________________________________________________________
____ _______________________________________________________________________________________________
_ __________ _______________________________________________________________________________________
__ _____ ___________________________________________________________________________________________
_ _ __ ______ ______________________________________________________________________________________
____________________________________________________________________________________________________
_  _  ___ ____ _____________________________________________________________________________________
____________________________________________________________________________________________________
_ _ ___ _______ ____________________________________________________________________________________
__ _______ _________________________________________________________________________________________
_ ______________ ___________________________________________________________________________________
____ _ _____________________________________________________________________________________________
_   _ __ __ _____ __________________________________________________________________________________
____________________________________________________________________________________________________
_ ________________ _________________________________________________________________________________
__ _________ _______________________________________________________________________________________
_ _  __ _ _________ ________________________________________________________________________________
____________________________________________________________________________________________________
_  __  ______ ______ _______________________________________________________________________________
____________________________________________________________________________________________________
_ _ ______ __________ ______________________________________________________________________________
__ _ ___ _____ _____________________________________________________________________________________
_ ____________________ _____________________________________________________________________________
____________________________________________________________________________________________________
_   _ _ ___ ___ _______ ____________________________________________________________________________
______ _____________________________________________________________________________________________
_ __ ____ ______________ ___________________________________________________________________________
__ _____________ ___________________________________________________________________________________
_ _ ________ ____________ __________________________________________________________________________
____________________________________________________________________________________________________
_  __ __ ________ ________ _________________________________________________________________________
____ _____ _________________________________________________________________________________________
_ _ __  _____ _____________ ________________________________________________________________________
__ _______________ _________________________________________________________________________________
_ __________________________ _______________________________________________________________________
____________________________________________________________________________________________________
_     ___ _ __ ____ _________ ______________________________________________________________________
____________________________________________________________________________________________________
_ ____________________________ _____________________________________________________________________
__ ___ _ ___________ _______________________________________________________________________________
_ _ ___ _______ _______________ ____________________________________________________________________
____ _______ _______________________________________________________________________________________
_  __ ____ __________ __________ ___________________________________________________________________
____________________________________________________________________________________________________
_ _ ____________ ________________ __________________________________________________________________
__ ___________________ _____________________________________________________________________________
_ __ _ __ ___ ____________________ _________________________________________________________________
____________________________________________________________________________________________________
_   _ _  __ _____ _____ ___________ ________________________________________________________________
____________________________________________________________________________________________________
_ __________________________________ _______________________________________________________________
__ _ _________ _________ ___________________________________________________________________________
_ _ ______________ __________________ ______________________________________________________________
______ ___ _________________________________________________________________________________________
_  __ ______ ____________ ____________ _____________________________________________________________
____________________________________________________________________________________________________
_ _  __ _ _____ ___ ___________________ ____________________________________________________________
__ _____ _________________ _________________________________________________________________________
_ ______________________________________ ___________________________________________________________
____________________________________________________________________________________________________
_   _  ____ _ ______ ______ _____________ __________________________________________________________
____ ___________ ___________________________________________________________________________________
_ ________________________________________ _________________________________________________________
__ _________________________ _______________________________________________________________________
_ _ ___ __ __________ _____________________ ________________________________________________________
____________________________________________________________________________________________________
_  _  __  ____ __ ___________ ______________ _______________________________________________________
______ _____ _______________________________________________________________________________________
_ _ __________________ ______________________ ______________________________________________________
__ ___________________________ _____________________________________________________________________
_ ____________________________________________ _____________________________________________________
____ _____________ _________________________________________________________________________________
_   _ _ ___ ___ _______ _______ _______________ ____________________________________________________
____________________________________________________________________________________________________
_ ____ ______ __________________________________ ___________________________________________________
__ _____ _ _____________________ ___________________________________________________________________
_ _  ____ _________ ____ ________________________ __________________________________________________

Agora, incluindo o vermelho extra especial Special Mega-Highlight © Highlight-Magic ™ Extended Edition ©: (clique na miniatura para ampliar)

Rubi com cor, 110 caracteres

puts (1..n=gets.to_i).map{|a|x=(2..n).map{|b|a!=b&&a%b==0? ' ':?_}.join;x.index(' ')??_+x :"\e[41m_#{x}\e[0m"}

Edição estendida

Maçaneta da porta
fonte
1
Parece que deve ser um fractal ...
Decay Beta 28/08
Remova o espaço dentro do ternário antes do ' '. Provavelmente atrapalha seu marcador de sintaxe, mas ainda funciona corretamente. Além disso,a%b<1
Value Ink
*''funcionará da mesma maneira que ingressar, e você pode procurar por, em a<bvez de, a!=bjá que nenhum fator de a é maior que a. Também pode haver economia ao cortar em uma sequência de dois caracteres com o resultado de algumas contas matemáticas em eb em vez de usar um ternário.
histocrat
5

J - 28 car

1('_ '{~0==+&|:1&=+|/~)@:+i.

Explicado por explosão:

1(                    )@:+i.  NB. on vector 1..n, do
                   |/~        NB. take the table "column modulo row"
               1&=+           NB. add 1 to column 1
          =                   NB. identity matrix of size 10
            &|:               NB. transpose both tables (now table is row mod col)
           +                  NB. add them
  '_ '{~0=                    NB. space if cell=0 else underscore

O que isso parece:

   1('_ '{~0==+&|:1&=+|/~)@:+i.25
_________________________
_________________________
_________________________
_ _______________________
_________________________
_  ______________________
_________________________
_ _ _____________________
__ ______________________
_ __ ____________________
_________________________
_   _ ___________________
_________________________
_ ____ __________________
__ _ ____________________
_ _ ___ _________________
_________________________
_  __ __ ________________
_________________________
_ _  ____ _______________
__ ___ __________________
_ ________ ______________
_________________________
_   _ _ ___ _____________
____ ____________________
algoritmshark
fonte
4

Python 2, 76 71

r=range(1,input()+1)
for i in r:print''.join("_ "[i%j<1<j<i]for j in r)

Não tenho certeza se ele pode ficar mais curto do que isso ... Essas palavras-chave: range, inpute printcustam muito.

Falko
fonte
3
Você pode substituir i>j>1and i%j<1pori>j>1>i%j
29/08/14
@ Sieg: Legal! Na verdade, é minha primeira vez explorando essas comparações concatenadas.
Falko
Eu escrevi esse código exato, caractere por caractere, até nomes var, incluindo o i%j<1<j<i:-P. Então talvez não fique mais curto.
Xnor
Na verdade, acho que (não testado) você pode fazer i%j<1. Isso implica i>=j.
seequ
@ Sii: Sim, mas precisamos i>j, não i>=jevitar espaços em branco na diagonal.
Falko
3

APL (28)

'_ '[(1+(1≠⊢)∧≠∧0=|⍨)/¨⍳2⍴⎕]

Explicação:

  • ⍳2⍴⎕: leia um número N e faça uma matriz de coordenadas N por N
  • (... )/¨: para cada par de coordenadas, aplique a seguinte função:
    • Uma célula deve ter um espaço se:
    • 0=|⍨: y modx = 0 e
    • ≠: x não é igual a y, e
    • 1≠⊢: x não é 1.
    • 1+: Adicione 1à matriz de bits resultante porque as matrizes APL começam em 1.
  • '_ '[... ]: substitua cada 1um por um sublinhado e 2por um espaço.
marinus
fonte
Aparentemente, 28 é o número mágico de golfe aqui.
2

Perl,    69   61

Versão atualizada (obrigado, Dennis !)

$n=<>;for$i(1..$n){say"_".join"",map{$i%$_|$i==$_?_:$"}2..$n}

Versão original:

$n=<>;for$i(1..$n){say"_".join("",map{$i%$_||$i==$_?"_":" "}(2..$n))}
Todd Lehman
fonte
1
1. Nem precisa joinnem 2..$nentre parênteses. 2. Com o -nswitch, você pode usar em $_vez de $n. 3. _é uma palavra de ordem válida, portanto não precisa de aspas. 4. Você pode usar em $"vez de " ". 5. Você pode usar em | vez de ||.
Dennis
@ Dennis - Obrigado! Eu apliquei alguns deles. Eu não fiz a -ncoisa porque queria manter um programa independente e não tenho que dizer $^N=1. O uso de _como uma palavra de barra funcionou no caso de, $i==_mas não funcionou no caso de, $i%_porque o analisador pensou que %_era um hash.
Todd Lehman
1
1. Você pode mantê-lo independente com um shebang ( #!/bin/perl -ngeralmente é contado como 1 byte), mas isso depende obviamente de você. Não tenho idéia do que $^N=1faz ... 2. $i==_não funcionará corretamente; testará se $i == "_". O que eu quis dizer é usar em _vez de "_", ie, say _e $i==$_?_:$".
Dennis
@ Dennis - ohhhh porcaria, você está certo. A edição que fiz introduziu uma linha diagonal através da matriz. Que vergonha por não ter percebido isso. Fixo. Eu vejo o que você quer dizer sobre _= "_"agora. Infelizmente, ele funciona no último caso, mas gera um erro próximo ao, sayporque parece achar que é uma manipulação de arquivo.
Todd Lehman
2

CJam, 27 bytes

q~:I,{__I?'_*S+I*I<'_t}%zN*

Experimente online.

Essa abordagem atinge a mesma contagem de bytes que minha outra resposta, mas achei que valeria a pena postar de qualquer maneira. Em vez de marcar múltiplos adequados em cada linha, ele faz exatamente o que a especificação diz.

Como funciona

q~:I                         " Read an integer I from STDIN.                              ";
    ,{                }%     " For each J ∊ {1,...,I}:                                    ";
          '_*S+              " Push J - 1 underscores followed by a space.                ";
               I*I<          " Repeat the pattern to complete I characters.               ";
       _I?                   " For the first row, replace all spaces with underscores.    ";
      _            '_t       " Replace the Jth character by an underscore.                ";
                        zN*  " Transpose rows and columns; separate with linefeeds.       ";

Exemplo de execução

$ cjam prime-lines.cjam <<< 10; echo
__________
__________
__________
_ ________
__________
_  _______
__________
_ _ ______
__ _______
_ __ _____
$ cjam prime-lines.cjam <<< 100 | md5sum # no trailing newline
83c7b974e1510f482322456a9dbb461f  -
Dennis
fonte
1

C, 143

C não é, obviamente, a escolha certa do idioma para isso. Mas, para completar, eis uma maneira possível de fazê-lo no C. Funciona para valores de n até 1048575. Lê n da entrada padrão.

#include <stdio.h>
main(){int n,i=0,j;scanf("%d",&n);char x[1<<20];x[n+1]=0;
for(;++i<=n;){for(j=0;++j<=n;)x[j]=i%j|i==j|j==1?95:32;puts(x+1);}}

É muito rápido, no entanto.

  • O tempo de execução para n = 1.000.000 (que produz uma grade de 1.000.000.000.000 de elementos) é de aproximadamente 55 minutos no meu sistema.

  • O tempo de execução para n = 1000 (que produz uma grade de 1.000.000 de elementos) é menor que 1/100 segundo.

Todd Lehman
fonte
4
1. A inclusão não é necessária para alguns compiladores (por exemplo, GCC), para que você possa removê-lo. 2. Variáveis ​​globais inicializam em 0 e padrão em int, para que você possa usar char x[1<<20];n,i,j;main.... 3. for(scanf("%d",&n);i++<n;)salva dois bytes acima scanf("%d",&n);for(;++i<=n;).
Dennis