Meine Primzahlen sind immer durchgezogene Linien

12

Erstellen wir ein N × N-Raster aus Leerzeichen und Unterstrichen, mit dem visuell festgestellt werden kann, ob eine Zahl eine Primzahl ist. (N kann eine beliebige positive ganze Zahl sein.)

Dieses Raster hat drei einfache Regeln:

  1. Die n-te Spalte enthält das wiederholte Muster von n-1 Unterstrichen, gefolgt von einem Leerzeichen. Dieses Muster beginnt in der ersten Zeile und endet möglicherweise in der Mitte der Zeile N. (Zeilen und Spalten sind 1-indiziert.)
  2. Die erste Spalte wird durch alle Unterstriche anstelle aller Leerzeichen ersetzt.
  3. Wenn irgendwo ein Leerzeichen vorkommt, entspricht der Zeilenindex dem Spaltenindex und wird durch einen Unterstrich ersetzt.

Beispiel: N = 10

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

Die Indizes dienen nur der Übersichtlichkeit. Das einfache Raster selbst (was Ihr Programm ausgeben muss) ist:

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

Beachte das:

  • Die erste Spalte enthält alle Unterstriche.
  • Die zweite Spalte enthält Unterstrich, Unterstrich usw., mit Ausnahme des Unterstrichs in Zeile 2.
  • Die dritte Spalte enthält Unterstreichungszeichen, Unterstreichungszeichen usw., mit Ausnahme des Unterstreichungszeichens in Zeile 3.
  • etc.

Beachten Sie außerdem, dass außer 1 nur Zeilen mit Primzahlen in jeder Spalte Unterstriche aufweisen.

Da sich Unterstriche über die gesamte Schriftbreite erstrecken, bildet jede Zeile mit Primzahlen eine durchgehende durchgezogene Linie. Es ist also visuell recht einfach zu überprüfen, ob eine Zahl eine Primzahl ist oder nicht. Überprüfen Sie einfach, ob die Linie in allen Spalten durchgehend ist. (Tatsächlich reicht ein Blick auf die Quadratwurzel des Zeilenindex aus, aber die Ausgabe dieses Rasters erscheint weniger elegant.)

Programm

Schreiben Sie ein Programm, das diese Gitter mit N über stdin (oder die nächstliegende Alternative) zeichnet. Die Ausgabe erfolgt nach stdout (oder nach der nächstgelegenen Alternative) und sollte nur Leerzeichen, Unterstriche und Zeilenumbrüche mit einer optionalen nachgestellten Zeile enthalten.

Der kürzeste Code gewinnt.

code-golf primes
quelle
Ich verstehe nicht, wie es die Primzahl bestimmt
Filip Bartuzi
5
@FilipBartuzi Vielleicht check out en.wikipedia.org/wiki/Sieve_of_Eratosthenes
"Die n-te Spalte enthält das wiederholte Muster von n-1 Unterstrichen, gefolgt von einem Leerzeichen." Sollte die Spalte n = 1 also nicht alle Leerzeichen sein, nicht alle Unterstriche?
Algorithmushai
6
Ich muss sagen, dass mir die Anforderung "Keine nachgestellten Zeilen" nicht besonders gefällt. Dies ist in einigen Sprachen sehr schwierig, in anderen völlig unmöglich und betrifft nur Programme, die auf STDOUT drucken.
Dennis
4
Die Beschreibung war für mich schwer zu verstehen. So würde ich es beschreiben: Beginnen Sie mit einem Raster von N Zeilen mit N Unterstrichen. nMachen Sie für die th-Zeile das kth-Zeichen zu einem Leerzeichen, wenn kes sich um einen Teiler mhandelt, der nicht 1 oder ist m.
Casey Chu

Antworten:

7

CJam, 33 28 27 Bytes

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

Probieren Sie es online aus.

Wie es funktioniert

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

Beispiellauf

$ cjam solid-primes.cjam <<< 10
__________
__________
__________
_ ________
__________
_  _______
__________
_ _ ______
__ _______
_ __ _____
$ cjam solid-primes.cjam <<< 100 | md5sum # trailing newline
e4396b316989813dada21141b569ccf9  -
Dennis
quelle
Ich werde eine Erklärung posten, wenn ich mit dem Golfen fertig bin.
Dennis
9
33 Bytes und du bist noch nicht fertig mit Golfen?
5

Ruby, 77 73 Zeichen

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

Einige Tricks, die ich benutzt habe:

  • Der ..Operator hat fast die niedrigste Priorität aller Operatoren in Ruby, (1..n=gets.to_i)funktioniert also einfach.

  • Anstatt ein Extra hinzuzufügen a!=1 Bedingung , wenn geprüft wird, ob das Zeichen ein Leerzeichen anstelle eines Unterstrichs sein soll (da die erste Zeile nur Unterstriche enthält), habe ich gerade den Bereich von gestartet 2und einem zusätzlichen vorangestellt ?_.

  • Zeile A kann zu Zeile B werden:

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

    weil ich ein extra Leerzeichen zwischen bund ?in Zeile A haben muss, das aber nicht zwischen 0und ?in Zeile B benötigt wird, b?ist aber eine gültige Ruby-Methode0? nicht.

  • puts werden Arrays automatisch mit Zeilenumbrüchen verbunden, sodass keine zusätzlichen Zeilen benötigt werden *"\n" .

Ausgabe für n=100 :

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

Jetzt inklusive Extra-Special ™ Mega-Buntes Rot © Highlight-Magic ™ ® Extended Edition ©: (zum Vergrößern auf das Bild klicken)

Ruby mit Farbe, 110 Zeichen

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"}

Erweiterte Version

Türknauf
quelle
1
Das sieht so aus, als sollte es ein Fraktal sein ...
Beta-Zerfall
Entfernen Sie das Leerzeichen im Ternär vor dem ' '. Wahrscheinlich bringt es Ihren Syntax-Textmarker durcheinander, aber es funktioniert immer noch einwandfrei. Also,a%b<1
Value Ink
*''die gleichen wie beitreten wird funktionieren, und Sie können überprüfen , a<bstatt , a!=bda kein Faktor a größer als ein. Es kann auch zu Einsparungen kommen, wenn Sie ein Segment in eine Zeichenfolge mit zwei Zeichen aufteilen, und zwar mit dem Ergebnis einiger Berechnungen für a und b, anstatt eine ternäre Zeichenfolge zu verwenden.
Histokrat
5

J - 28 Zeichen

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

Erklärt durch Explosion:

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

Wie es aussieht:

   1('_ '{~0==+&|:1&=+|/~)@:+i.25
_________________________
_________________________
_________________________
_ _______________________
_________________________
_  ______________________
_________________________
_ _ _____________________
__ ______________________
_ __ ____________________
_________________________
_   _ ___________________
_________________________
_ ____ __________________
__ _ ____________________
_ _ ___ _________________
_________________________
_  __ __ ________________
_________________________
_ _  ____ _______________
__ ___ __________________
_ ________ ______________
_________________________
_   _ _ ___ _____________
____ ____________________
algorithmshark
quelle
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)

Nicht sicher , ob es bekommen kann jede kürzer als diese ... Diese Stichworte: range, inputund printkostet ziemlich viel.

Falko
quelle
3
Sie können ersetzen i>j>1and i%j<1durchi>j>1>i%j
siehe auch
@ Sieg: Cool! Eigentlich nutze ich diese verketteten Vergleiche zum ersten Mal.
Falko
Ich hatte genau diesen Code Zeichen für Zeichen bis hin zu Var-Namen geschrieben, einschließlich i%j<1<j<i:-P. Vielleicht wird es wirklich nicht kürzer.
Xnor
Eigentlich denke ich, dass (nicht getestet) Sie tun können i%j<1. Es impliziert i>=j.
Siehe auch
@Sieg: Ja, aber wir müssen i>j, i>=jum Leerzeichen auf der Diagonale nicht zu vermeiden.
Falko
3

APL (28)

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

Erläuterung:

  • ⍳2⍴⎕: Lies eine Zahl N und erstelle eine N-mal-N-Koordinatenmatrix
  • (... )/¨: Wenden Sie für jedes Koordinatenpaar die folgende Funktion an:
    • Eine Zelle muss ein Leerzeichen haben, wenn:
    • 0=|⍨: y mod x = 0 und
    • ≠: x ist nicht gleich y und
    • 1≠⊢: x ist nicht 1.
    • 1+: 1Zur resultierenden Bitmatrix hinzufügen, da APL-Arrays bei 1 beginnen.
  • '_ '[... ]: Ersetzen Sie jeweils 1durch einen Unterstrich und 2ein Leerzeichen.
Marinus
quelle
Anscheinend ist 28 die magische Golfnummer hier.
2

Perl,    69   61

Aktualisierte Version (danke, Dennis !)

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

Originalfassung:

$n=<>;for$i(1..$n){say"_".join("",map{$i%$_||$i==$_?"_":" "}(2..$n))}
Todd Lehman
quelle
1
1. Weder Klammern joinnoch 2..$nNotwendigkeit. 2. Mit dem -nSchalter können Sie $_anstelle von verwenden $n. 3. _ist ein gültiges Bareword, daher sind keine Anführungszeichen erforderlich. 4. Sie können $"anstelle von verwenden " ". 5. Sie können | anstelle von verwenden ||.
Dennis
@ Tennis - Danke! Ich habe einige davon angewendet. Ich habe das -nDing nicht gemacht , weil ich es als eigenständiges Programm behalten wollte und nicht sagen muss $^N=1. Die Verwendung _als Bareword funktionierte im Fall von $i==_, funktionierte aber nicht im Fall von, $i%_weil der Parser-Gedanke %_ein Hash war.
Todd Lehman
1
1. Sie können es mit einem Shebang in sich geschlossen halten ( #!/bin/perl -nwird normalerweise als 1 Byte gezählt), aber das liegt natürlich an Ihnen. Ich habe keine Ahnung, was $^N=1... 2. $i==_nicht richtig funktioniert; es wird testen ob $i == "_". Was ich meinte, ist die Verwendung _von "_", dh say _und $i==$_?_:$".
Dennis
@ Tennis - ohhhh Mist, du hast recht. Die von mir vorgenommene Bearbeitung führte eine diagonale Linie durch die Matrix. Schade, dass ich das nicht verstanden habe. Fest. Ich sehe , was Sie bedeuten _= "_"jetzt. Leider funktioniert es im letzteren Fall, aber es gibt mir einen Fehler neben dem, sayweil es scheint, als wäre es ein Dateihandle.
Todd Lehman
2

CJam, 27 Bytes

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

Probieren Sie es online aus.

Dieser Ansatz erreicht die gleiche Byteanzahl wie meine andere Antwort, aber ich dachte, dass es sich trotzdem lohnt, etwas zu posten. Anstatt in jeder Zeile die richtigen Vielfachen zu markieren, wird genau das getan, was in der Spezifikation angegeben ist.

Wie es funktioniert

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.       ";

Beispiellauf

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

C 143

C ist offensichtlich nicht die richtige Wahl der Sprache dafür. Der Vollständigkeit halber ist hier eine Möglichkeit, dies in C zu tun. Funktioniert für Werte von n bis 1048575. Liest n von der Standardeingabe.

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

Es ist jedoch sehr schnell.

  • Die Laufzeit für n = 1.000.000 (was ein Raster mit 1.000.000.000.000 Elementen ergibt) beträgt auf meinem System ungefähr 55 Minuten.

  • Die Laufzeit für n = 1000 (was ein Raster mit 1.000.000 Elementen ergibt) beträgt weniger als 1/100 Sekunde.

Todd Lehman
quelle
4
1. Für einige Compiler (z. B. GCC) wird das Include nicht benötigt, sodass Sie es entfernen können. 2. Globale Variablen werden auf 0 und standardmäßig auf initialisiert int, damit Sie sie verwenden können char x[1<<20];n,i,j;main.... 3. for(scanf("%d",&n);i++<n;)speichert zwei Bytes über scanf("%d",&n);for(;++i<=n;).
Dennis