Estos principios míos son siempre líneas sólidas

12

Creemos una cuadrícula N × N de espacios y guiones bajos que se puedan usar para determinar visualmente si un número es primo. (N puede ser cualquier número entero positivo).

Esta cuadrícula tiene tres reglas simples:

  1. La enésima columna contiene el patrón repetido de n - 1 guiones bajos seguido de un espacio. Este patrón comienza en la primera fila y se detiene, posiblemente a mitad del patrón, en la fila N. (Las filas y las columnas están indexadas en 1).
  2. La primera columna se reemplaza con todos los guiones bajos en lugar de todos los espacios.
  3. Si ocurre un espacio en algún lugar, el índice de la fila es igual al índice de la columna, se reemplaza con un guión bajo.

Ejemplo: N = 10

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

Los índices son solo por claridad. La cuadrícula simple (lo que debe generar su programa) es:

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

Darse cuenta de:

  • La primera columna es todos los guiones bajos.
  • La segunda columna va en subrayado, subrayado, etc., excepto el subrayado en la fila 2.
  • La tercera columna va en subrayado, subrayado, subrayado, subrayado, subrayado, etc., excepto el subrayado en la fila 3.
  • etc.

Observe también que, además de 1, solo las filas con números primos tienen guiones bajos en cada columna.

Como los guiones bajos abarcan todo el ancho de la fuente, cada fila numerada principal forma una línea continua continua. Por lo tanto, verificar si un número es primo o no es bastante fácil visualmente; solo verifique si su línea es sólida en todas las columnas. (De hecho, mirar hacia la raíz cuadrada del índice de fila es suficiente, pero generar esa cuadrícula parece menos elegante).

Programa

Escriba un programa que dibuje estas cuadrículas dado N a través de stdin (o la alternativa más cercana). La salida va a stdout (o la alternativa más cercana) y solo debe contener espacios, guiones bajos y nuevas líneas, con una nueva línea final opcional.

El código más corto gana.

code-golf primes
fuente
No entiendo cómo determina el número primo
Filip Bartuzi
55
@FilipBartuzi Quizás visite en.wikipedia.org/wiki/Sieve_of_Eratosthenes
"La enésima columna contiene el patrón repetido de n - 1 guiones bajos seguido de un espacio". Entonces, ¿no debería la columna n = 1 ser todos los espacios, no todos los guiones bajos?
algorithmshark
66
Debo decir que no me gusta especialmente el requisito de "nueva línea final". Esto es muy difícil en algunos idiomas, totalmente imposible en otros y solo afecta a los programas que se imprimen en STDOUT.
Dennis
44
La descripción me fue difícil de entender. Así es como lo describiría: Comience con una cuadrícula de N líneas de N guiones bajos. Para la nlínea th, haga que el kcarácter th sea un espacio si kes un divisor de meso no es 1 o m.
Casey Chu

Respuestas:

7

CJam, 33 28 27 bytes

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

Pruébalo en línea.

Cómo 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.                                                               ";
}         "                                                                               ";

Ejecución de ejemplo

$ cjam solid-primes.cjam <<< 10
__________
__________
__________
_ ________
__________
_  _______
__________
_ _ ______
__ _______
_ __ _____
$ cjam solid-primes.cjam <<< 100 | md5sum # trailing newline
e4396b316989813dada21141b569ccf9  -
Dennis
fuente
Publicaré una explicación cuando termine de jugar al golf.
Dennis
99
33 bytes y no has terminado de jugar al golf?
5

Ruby, 77 73 caracteres

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

Algunos trucos que utilicé:

  • El ..operador tiene casi la precedencia más baja de todos los operadores en Ruby, por lo que (1..n=gets.to_i)simplemente funciona.

  • En lugar de agregar una a!=1condición adicional al verificar para ver si el carácter debe ser un espacio en lugar de un guión bajo (dado que la primera fila es todos los guiones bajos), acabo de comenzar el rango 2y agregué un extra ?_.

  • La línea A puede convertirse en la línea B:

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

    porque tengo que tener un espacio extra entre by ?en la línea A, pero eso no es necesario entre 0y ?en la línea B. b?Es un método válido de Ruby, pero 0?no lo es.

  • putsautomáticamente unirá matrices con nuevas líneas para usted, eliminando la necesidad de un extra *"\n".

Salida para n=100:

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

Ahora incluye Extra-Special ™ Mega-Colorful Red © Highlight-Magic ™ ® Extended Edition ©: (haga clic en la miniatura para ampliarla)

Rubí con color, 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"}

Edición extendida

Pomo de la puerta
fuente
1
Parece que debería ser un fractal ...
Beta Decay
Elimine el espacio dentro del ternario antes del ' '. Probablemente estropea su resaltador de sintaxis, pero aún funciona correctamente. Además,a%b<1
Value Ink el
*''funcionará igual que join, y puede verificarlo en a<blugar de hacerlo, a!=bya que ningún factor de a es mayor que a. También podría haber ahorros al cortar en una cadena de dos caracteres con el resultado de algunas matemáticas en ayb en lugar de usar un ternario.
histocrat
5

J - 28 char

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

Explicado por explosión:

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

Cómo se ve:

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

Pitón 2, 76 71

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

No estoy seguro si puede conseguir nada más corto que esto ... Estas palabras clave: range, inputy printcuesta mucho.

Falko
fuente
3
Puede reemplazar i>j>1and i%j<1coni>j>1>i%j
seequ
@Sieg: ¡Genial! En realidad, es la primera vez que exploto estas comparaciones concatenadas.
Falko
Había escrito este código exacto carácter por carácter hasta varios nombres, incluido el i%j<1<j<i:-P. Entonces, tal vez realmente no se acorte más.
xnor
En realidad, creo (no probado) que puedes hacer i%j<1. Implica i>=j.
seequ
@Sieg: Sí, pero necesitamos i>jno i>=jevitar espacios en blanco en la diagonal.
Falko
3

APL (28)

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

Explicación:

  • ⍳2⍴⎕: lee un número N y crea una matriz de coordenadas N-por-N
  • (... )/¨: para cada par de coordenadas, aplique la siguiente función:
    • Una celda debe tener un espacio si:
    • 0=|⍨: y modx = 0, y
    • ≠: x no es igual a y, y
    • 1≠⊢: x no lo es 1.
    • 1+: Agregue 1a la matriz de bits resultante porque las matrices APL comienzan en 1.
  • '_ '[... ]: reemplace cada uno 1con un guión bajo y 2con un espacio.
marinus
fuente
Aparentemente 28 es el número mágico de golf aquí.
2

Perl,    69   61

Versión actualizada (¡gracias, Dennis !)

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

Versión original:

$n=<>;for$i(1..$n){say"_".join("",map{$i%$_||$i==$_?"_":" "}(2..$n))}
Todd Lehman
fuente
1
1. Ni jointampoco 2..$nnecesitan paréntesis. 2. Con el -ninterruptor, puede usar en $_lugar de $n. 3. _es una palabra válida, por lo que no necesita comillas. 4. Puede usar en $"lugar de " ". 5. Puede usar en | lugar de ||.
Dennis
@ Dennis - ¡Gracias! Apliqué algunos de esos. No hice la -ncosa porque quería mantenerlo como un programa autónomo y no tener que decirlo $^N=1. El uso de _como una palabra simple funcionó en el caso de, $i==_pero no funcionó $i%_porque el analizador pensó que %_era un hash.
Todd Lehman
1
1. Puede mantenerlo autónomo con un shebang ( #!/bin/perl -ngeneralmente se cuenta como 1 byte), pero eso obviamente depende de usted. No tengo idea de lo que $^N=1hace ... 2. $i==_no funcionará correctamente; probará si $i == "_". Lo que quise decir es usar en _lugar de "_", es decir, say _y $i==$_?_:$".
Dennis
@ Dennis - ohhhh mierda, tienes razón. La edición que hice introdujo una línea diagonal a través de la matriz. Qué pena por no haberlo entendido. Fijo. Ya veo a qué te refieres con _= "_"ahora. Desafortunadamente, funciona en el último caso, pero me da un error al lado sayporque parece pensar que es un controlador de archivo.
Todd Lehman
2

CJam, 27 bytes

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

Pruébalo en línea.

Este enfoque logra el mismo número de bytes que mi otra respuesta, pero pensé que valía la pena publicarlo de todos modos. En lugar de marcar los múltiplos adecuados en cada fila, hace exactamente lo que dice la especificación.

Cómo 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.       ";

Ejecución de ejemplo

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

C, 143

C obviamente no es la elección correcta del lenguaje para esto. Pero para completar, aquí hay una forma posible de hacerlo en C. Funciona para valores de n hasta 1048575. Lee n de la entrada estándar.

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

Sin embargo, es muy rápido.

  • El tiempo de ejecución para n = 1,000,000 (que produce una cuadrícula de 1,000,000,000,000 elementos) es de aproximadamente 55 minutos en mi sistema.

  • El tiempo de ejecución para n = 1000 (que produce una cuadrícula de 1,000,000 de elementos) es inferior a 1/100 de segundo.

Todd Lehman
fuente
44
1. La inclusión no es necesaria para algunos compiladores (por ejemplo, GCC), por lo que puede eliminarla. 2. Las variables globales se inicializan en 0 y por defecto son int, para que pueda usar char x[1<<20];n,i,j;main.... 3. for(scanf("%d",&n);i++<n;)ahorra dos bytes scanf("%d",&n);for(;++i<=n;).
Dennis