Ist diese Zahl eine Primzahl?

195

Ob Sie es glauben oder nicht, wir haben noch keine Code Golf Challenge für einen einfachen Primalitätstest . Während es nicht unbedingt die interessanteste Herausforderung ist, insbesondere für "gewöhnliche" Sprachen, kann es in vielen Sprachen nicht trivial sein.

Der Rosetta-Code enthält Listen nach Sprache der idiomatischen Herangehensweisen an Primärtests, wobei einer speziell den Miller-Rabin-Test verwendet und der andere die Probedivision verwendet . Das "idiomatischste" stimmt jedoch oft nicht mit dem "kürzesten" überein. In dem Bestreben, Programming Puzzles und Code Golf zur Anlaufstelle für Code Golf zu machen, soll mit dieser Herausforderung ein Katalog mit den kürzesten Ansätzen in jeder Sprache erstellt werden, ähnlich wie bei "Hello, World!" und Golf du ein Quine für großes Wohl! .

Darüber hinaus ist die Fähigkeit zur Implementierung eines Primalitätstests Teil unserer Definition der Programmiersprache , sodass diese Herausforderung auch als Verzeichnis bewährter Programmiersprachen dienen wird.

Aufgabe

Schreiben Sie ein vollständiges Programm , das bei einer streng positiven Ganzzahl n als Eingabe bestimmt, ob n eine Primzahl ist, und entsprechend einen Wahrheits- oder Falschwert ausgibt .

Für diese Herausforderung ist eine Ganzzahl eine Primzahl, wenn sie genau zwei streng positive Teiler hat. Beachten Sie, dass dies 1 ausschließt , das der einzige rein positive Teiler ist.

Ihr Algorithmus muss deterministisch sein (dh mit Wahrscheinlichkeit 1 die richtige Ausgabe erzeugen) und sollte theoretisch für beliebig große ganze Zahlen funktionieren. In der Praxis können Sie davon ausgehen, dass die Eingabe in Ihrem Datentyp gespeichert werden kann, solange das Programm für ganze Zahlen von 1 bis 255 arbeitet.

Eingang

  • Wenn Ihre Sprache in der Lage ist, aus STDIN zu lesen, Befehlszeilenargumente oder eine andere alternative Form der Benutzereingabe zu akzeptieren, können Sie die Ganzzahl als Dezimalrepräsentation, unäre Repräsentation (unter Verwendung eines Zeichens Ihrer Wahl), Bytearray (groß oder klein) lesen Little Endian) oder Single Byte (wenn dies der größte Datentyp Ihrer Sprache ist).

  • Wenn (und nur wenn) Ihre Sprache keine Benutzereingaben akzeptieren kann, können Sie die Eingaben in Ihrem Programm fest codieren.

    In diesem Fall muss die fest codierte Ganzzahl leicht austauschbar sein. Insbesondere darf es nur an einer Stelle im gesamten Programm erscheinen.

    Reichen Sie für Bewertungszwecke das Programm ein, das der Eingabe 1 entspricht .

Ausgabe

Die Ausgabe muss auf STDOUT oder die nächstgelegene Alternative geschrieben werden.

Wenn möglich, sollte die Ausgabe nur aus einem Wahrheits- oder Falschwert (oder einer Zeichenfolgendarstellung davon) bestehen, optional gefolgt von einer einzelnen neuen Zeile.

Die einzige Ausnahme von dieser Regel ist die konstante Ausgabe des Interpreters Ihrer Sprache, die nicht unterdrückt werden kann, z. B. eine Begrüßung, ANSI-Farbcodes oder Einrückungen.

Zusätzliche Regeln

  • Dabei geht es nicht darum, die Sprache mit dem kürzesten Ansatz für Primärtests zu finden, sondern in jeder Sprache den kürzesten Ansatz zu finden. Daher wird keine Antwort als angenommen markiert.

  • Einsendungen in den meisten Sprachen werden in Bytes in einer geeigneten, bereits vorhandenen Codierung bewertet, normalerweise (aber nicht unbedingt) in UTF-8.

    Die Sprache Piet wird zum Beispiel in Codels bewertet, was die natürliche Wahl für diese Sprache ist.

    Einige Sprachen, wie Ordner , sind etwas schwierig zu bewerten. Im Zweifelsfall bitte nach Meta fragen .

  • Im Gegensatz zu unseren üblichen Regeln können Sie eine Sprache (oder Sprachversion) auch dann verwenden, wenn diese neuer als diese Herausforderung ist. Wenn jemand dies missbrauchen möchte, indem er eine Sprache erstellt, in der das leere Programm einen Primalitätstest durchführt, dann gratuliert er, dass er den Weg für eine sehr langweilige Antwort ebnet.

    Beachten Sie, dass ein Dolmetscher vorhanden sein muss, damit die Einreichung getestet werden kann. Es ist erlaubt (und sogar empfohlen), diesen Dolmetscher für eine zuvor nicht implementierte Sprache selbst zu schreiben.

  • Wenn Ihre bevorzugte Sprache eine triviale Variante einer anderen (möglicherweise populäreren) Sprache ist, die bereits eine Antwort enthält (denken Sie an BASIC- oder SQL-Dialekte, Unix-Shells oder triviale Brainfuck-Derivate wie Headsecks oder Unary), sollten Sie der vorhandenen Antwort eine Anmerkung hinzufügen Die gleiche oder eine sehr ähnliche Lösung ist auch in der anderen Sprache die kürzeste.

  • Eingebaute Funktionen zum Testen der Primalität sind zulässig. Mit dieser Herausforderung soll die kürzestmögliche Lösung in jeder Sprache katalogisiert werden. Wenn es also kürzer ist, eine in Ihrer Sprache integrierte Lösung zu verwenden, entscheiden Sie sich für diese.

  • Sofern sie nicht zuvor außer Kraft gesetzt wurden, gelten alle Standardregeln für Code-Golf , einschließlich der http://meta.codegolf.stackexchange.com/q/1061 .

Bitte stimmen Sie langweiligen (aber gültigen) Antworten in Sprachen nicht ab, in denen es nicht viel zum Golfen gibt. Diese sind für diese Frage nach wie vor hilfreich, da versucht wird, einen Katalog so vollständig wie möglich zusammenzustellen. Stimmen Sie Antworten jedoch in erster Linie in Sprachen ab, in denen sich der Autor tatsächlich um das Golfen des Codes bemühen musste.

Katalog

Das Stapel-Snippet am Ende dieses Beitrags generiert den Katalog aus den Antworten a) als Liste der kürzesten Lösungen pro Sprache und b) als Gesamt-Bestenliste.

Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

## Language Name, N bytes

Wo Nist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:

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

Wenn Sie mehrere Zahlen in Ihre Kopfzeile aufnehmen möchten (z. B. weil Ihre Punktzahl die Summe von zwei Dateien ist oder wenn Sie die Strafen für Interpreter-Flags separat auflisten möchten), stellen Sie sicher, dass die tatsächliche Punktzahl die letzte Zahl in der Kopfzeile ist:

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

Sie können den Namen der Sprache auch als Link festlegen, der dann im Snippet angezeigt wird:

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

Code-Snippet anzeigen

code-golf number number-theory primes decision-problem Dennis
quelle
Kann ich Eingaben als negative Zahlen annehmen, wobei abs (Eingabe) die Zahl ist, die ich teste?
Stan Strum
Nein, die Eingabe ist eine rein positive Ganzzahl.
Dennis
1
@LyndonWhite Dies war als Katalog (wie „Hello, World!“ ) Von Primalitätstests gedacht , daher schien ein einheitliches Übermittlungsformat vorzuziehen. Es ist eine von zwei Entscheidungen in Bezug auf diese Herausforderung, die ich bedaure. Die andere Entscheidung erlaubt nur deterministische Primalitätstests.
Dennis
1
@ Shaggy Scheint eine Frage für Meta.
Dennis
1
Ja, das habe ich mir gedacht. Ich werde Sie die Ehre erweisen lassen, da es Ihre Herausforderung ist.
Shaggy

Antworten:

225

Hallo Welt! , 13

hello, world!
Histokrat
quelle
83
Haben Sie, wie, einfach zu erstellen , um diese Sprache, nur für die Vorlage? ;)
ETHproductions
41
@ETHproductions Sieht so aus, als ob die letzte Übergabe vor 10 Tagen erfolgte.
Geobits
39
Ich hatte gehofft, die Sprache in einem etwas besseren Zustand zu haben, bevor ich irgendwo darauf verlinke, aber diese Herausforderung wurde veröffentlicht und ich konnte nicht widerstehen.
Histokrat
31
Ich würde fast sagen, dass das Hängen an einer Eingabe von 1 die richtige Funktionalität ist.
iamnotmaynard
21
Das Beste daran ist, dass das Programm nicht nur ein integriertes Programm ist, sondern dass jeder Charakter seine eigene Rolle spielt, um das richtige Ergebnis zu erzielen.
ETHproductions
157

Hexagony , 29 Bytes

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

Die lesbare Version dieses Codes lautet:

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

Erläuterung: Es wird geprüft, ob es eine Zahl von 2 bis n-1 gibt, die n dividiert.

Initialisierung:

Schreibe n in eine Speicherzelle und n-1 in eine andere:

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

Sonderfall n = 1:

0 ausgeben und beenden

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

Die Schleife

Berechnen Sie n% a und verringern Sie a. Beenden Sie, wenn a = 1 oder n% a = 0 ist.

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

Fall a = 1:

Erhöhe eine 0 zu einer 1, drucke sie aus und beende sie. (Der Befehlszeiger läuft in nordöstlicher Richtung und durchläuft eine Schleife von der östlichen zur südwestlichen Ecke. Und das $ sorgt dafür, dass der nächste Befehl ignoriert wird.)

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

Fall a% n = 0:

0 ausgeben und beenden (Der Anweisungszeiger führt SW aus und springt nach oben zum @

   . . . .
  . . @ . .
 . . . . . >
. . . . . ! .
 . . . . . .
  . . . . .
   . . . .
Etoplay
quelle
61
Heiliger Mist, das ist ein beeindruckender erster Beitrag. :) Ich werde das Kopfgeld sofort einsetzen (ich werde es in 7 Tagen vergeben, um mehr Aufmerksamkeit auf Ihre Antwort zu lenken). Willkommen bei PPCG!
Martin Ender,
35
Gute Antwort! +1 für " Die lesbare Version dieses Codes ist: <...> " :-)
seit dem
68

Hexagony , 218 92 58 55 Bytes

Hinweis: Diese Antwort wurde von Etoplay mit einer Lösung mit Seitenlänge 4 deutlich übertroffen.

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

Das erste nicht-triviale (dh nicht-lineare) Hexagony-Programm! Es basiert auf dem gleichen quadratischen Ansatz wie die Labyrinth-Antwort von Sp3000 . Nachdem ich mit einem Hexagon der Größe 10 angefangen hatte, konnte ich es auf die Größe 5 komprimieren. Allerdings konnte ich einen doppelten Code wiederverwenden, und es gibt immer noch eine ganze Reihe von No-Ops im Code, also könnte Größe 4 genau das Richtige sein möglich sein.

Erläuterung

Um den Code zu verstehen, müssen wir ihn zuerst aufklappen. Hexagony füllt jeden Quellcode mit No-Ops ( .) auf die nächste zentrierte hexagonale Zahl auf 61. Anschließend wird der Code in ein reguläres Sechseck der entsprechenden Größe umgeordnet:

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

Dies ist mit überkreuzenden und überlappenden Ausführungspfaden und mehreren Anweisungszeigern (IPs) ziemlich schwierig. Um zu erklären, wie es funktioniert, schauen wir uns zunächst eine ungolfed-Version an, bei der der Kontrollfluss nicht durch die Ränder geht, nur eine IP verwendet wird und die Ausführungspfade so einfach wie möglich sind:

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

Randnotiz: Der obige Code beginnt mit der Ausführung der ersten Zeile, die voller No-Ops ist. Wenn die IP die Nordostkante erreicht, wird sie in die äußerste linke Ecke (die )) umgebrochen , in der der eigentliche Code beginnt.

Bevor wir beginnen, ein Wort zum Speicherlayout von Hexagony. Es ist ein bisschen wie Brainfucks Band über Steroide. Tatsächlich handelt es sich nicht um ein Band, sondern um ein hexagonales Gitter selbst (ein unendliches), bei dem jede Kante einen ganzzahligen Wert aufweist, der anfänglich 0 ist (und im Gegensatz zu Standard-Brainfuck sind die Werte Ganzzahlen mit willkürlicher Genauigkeit). Für dieses Programm verwenden wir vier Kanten:

Bildbeschreibung hier eingeben

Wir werden die Fakultät an Kante A berechnen , unsere Eingabe an Kante C herunterzählen und eine weitere Kopie der Eingabe (für das Modulo) an Kante D speichern . B wird als temporäre Flanke für Berechnungen verwendet.

Der Speicherzeiger (MP) beginnt an der Kante A und zeigt nach Norden (dies ist wichtig, um den MP zu bewegen). Hier ist das erste Bit des Codes:

)}?}=&{

)Inkrementiert Kante A auf 1als Basis der Fakultät. }Der MP macht eine Rechtskurve, dh er bewegt sich zu Kante C (nach Nordosten zeigend). Hier lesen wir die Eingabe als Ganzzahl mit ?. Dann machen wir noch eine Rechtskurve bis zur Kante D mit }. =Kehrt den MP so um, dass er auf den mit C geteilten Scheitelpunkt zeigt . &kopiert den Wert von C (der Eingabe) nach D - der Wert wird von links kopiert, da der aktuelle Wert nicht positiv ist (Null). Schließlich machen wir die MP auf eine Linkskurve zurück C mit {.

Als nächstes <ist technisch eine Verzweigung, aber wir wissen, dass der aktuelle Wert positiv ist, so dass die IP immer nach rechts abbiegen wird >. Ein Branchentreffer von der Seite wirkt wie ein Spiegel, so dass sich die IP wieder horizontal in Richtung der bewegt (, was den Wert in C dekrementiert .

Die nächste Filiale <ist eigentlich eine Filiale. So laufen wir von n-1unten nach 1. Während der aktuelle Wert in C positiv ist, dreht sich die IP nach rechts (um die Schleife auszuführen). Sobald wir die Null erreicht haben, biegt sie stattdessen links ab.

Schauen wir uns die Schleife "body" an. Das |ist einfacher Spiegel, die >und <wird auch als Spiegel wieder verwendet. Das heißt, der eigentliche Schleifenkörper läuft auf

}=)&}=*}=

}Bewegt den MP zu Kante B und =kehrt seine Richtung zum Scheitelpunkt ABC um . )erhöht den Wert: Dies ist nur für die erste Iteration relevant, bei der der Wert von B immer noch Null ist. Wir möchten sicherstellen, dass er positiv ist, sodass der nächste Befehl &den rechten Nachbarn kopiert , dh A , dh den aktuellen Wert der Fakultät Berechnung, in B .

}Verschiebt dann den MP nach A und =kehrt ihn erneut um, um zum gemeinsamen Scheitelpunkt zu zeigen. *multipliziert beide Nachbarn, das heißt Kanten B und C und speichert das Ergebnis in A . Schließlich müssen wir noch }=zu C zurückkehren , das immer noch dem Scheitelpunkt ABC zugewandt ist .

Ich hoffe, Sie können sehen, wie dies die Fakultät von n-1in A berechnet .

Nun haben wir es geschafft, der Schleifenzähler in C ist Null. Wir wollen die Fakultät quadrieren und dann das Modulo mit der Eingabe nehmen. Das macht dieser Code:

&}=*{&'%!@

Da C Null ist , &Kopien der linke Nachbar, das heißt die Fakultäts in A . }=*bewegt sich zu B und das Produkt der beiden Kopien des faktoriellen (dh das Quadrat) in den Speichern B . kehrt {zu C zurück , kehrt den MP jedoch nicht um. Wir wissen , dass der aktuelle Wert nun positiv ist, so &Kopien Eingabe von D in C . 'das MP rückwärts nach rechts, auf dh A . Denken Sie daran, das Quadrat der faktoriellen ist in B und der Eingang in C . So %berechnet (n-1)!^2 % n, genau das, was wir suchen.!gibt das Ergebnis als Ganzzahl (0 oder 1) aus und @beendet das Programm.

Okay, aber das war die ungolfed version. Was ist mit der Golfversion? Sie müssen zwei weitere Dinge über Hexagony wissen:

  1. Die Ränder winden sich um. Wenn die IP auf eine Kante des Sechsecks trifft, springt sie zur gegenüberliegenden Kante. Dies ist nicht eindeutig, wenn die IP auf eine Ecke trifft. Wenn also eine Ecke getroffen wird, fungiert dies auch als Verzweigung: Wenn der aktuelle Wert positiv ist, springt die IP zur rechten Rasterkante, ansonsten zur linken.
  2. Es gibt tatsächlich 6 IPs. Jeder von ihnen beginnt in einer anderen Ecke und bewegt sich entlang der Kante im Uhrzeigersinn. Es ist immer nur eine IP-Adresse aktiv, dh Sie können die anderen 5 IP-Adressen einfach ignorieren, wenn Sie sie nicht möchten. Sie können mit zur nächsten IP (im Uhrzeigersinn) ]und mit zur vorherigen IP wechseln [. (Sie können auch ein bestimmtes mit wählen #, aber das ist für ein anderes Mal.)

Es gibt auch ein paar neue Befehle: \und /sind wie Spiegel |und ~multipliziert den aktuellen Wert mit -1.

Wie übersetzt sich die ungolfed-Version in die golfed-Version? Den linearen Einrichtungscode )}?}=&{und die grundlegende Schleifenstruktur finden Sie hier:

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

Jetzt überquert der Schleifenkörper einige Male die Kanten, aber am wichtigsten ist, dass die eigentliche Berechnung an die vorherige IP übergeben wird (die an der linken Ecke beginnt und sich nach Nordosten bewegt):

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

Nach dem Abprallen vom Ast in Richtung Südosten wickelt sich die IP um den Rand zu den beiden =in der oberen linken Ecke (die zusammen ein No-Op sind) und prallt dann vom /. Das ~invertiert das Vorzeichen des aktuellen Werts, was für nachfolgende Iterationen wichtig ist. Die IP wickelt sich wieder um dieselbe Kante und trifft schließlich, [wo die Kontrolle an die andere IP übergeben wird.

Dieser führt nun aus, ~}=)&}=*}was die Negation rückgängig macht und führt dann nur den ungolften Schleifenkörper (abzüglich des =) aus. Schließlich trifft es, ]welche Hände auf die ursprüngliche IP zurücksteuern. (Beachten Sie, dass diese IP beim nächsten Ausführen an der Stelle beginnt, an der sie aufgehört hat, sodass sie zuerst die Ecke berührt. Der aktuelle Wert muss negativ sein, damit die IP zum Nordwestrand zurückspringt anstelle des Südostens.)

Sobald die ursprüngliche IP die Kontrolle wieder aufnimmt, prallt sie von der ab \, führt die verbleibenden aus =und trifft dann >, um in die nächste Schleifeniteration einzuspeisen.

Nun der wirklich verrückte Teil: Was passiert, wenn die Schleife endet?

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

Die IP bewegt sich nordöstlich von der <und verläuft in nordöstlicher Diagonale. Es endet also auf demselben Ausführungspfad wie der Schleifenkörper ( &}=*}]). Was eigentlich ziemlich cool ist, denn genau das ist der Code, den wir an dieser Stelle ausführen möchten, zumindest wenn wir einen weiteren hinzufügen =}(weil }=}äquivalent zu {). Aber wie kommt das eigentlich nicht wieder in die frühere Schleife? Weil ]sich die nächste IP ändert, die jetzt die (bisher nicht verwendete) IP ist, die in der oberen rechten Ecke beginnt und sich nach Südwesten bewegt. Von dort aus wird die IP entlang der Kante fortgesetzt, bis zur oberen linken Ecke umgebrochen, die Diagonale nach unten verschoben, von der abgeprallt |und bei der @Ausführung des letzten Bits des linearen Codes beendet:

=}&)('%!@

(Das )(ist natürlich ein No-Op - ich musste das hinzufügen, (weil das )schon da war.)

Puh ... was für ein Durcheinander ...

Martin Ender
quelle
Nett! Wie neu ist das Außerdem möchten Sie möglicherweise eine Esolangs-Seite erstellen, wenn Sie eine stabile Version erhalten
mbomb007
18
@ mbomb007 Ich habe die Sprache vor zwei Tagen implementiert (und sie vor zwei oder drei Tagen entworfen). Und ja, ich werde definitiv eine Esolangs-Seite hinzufügen, aber ich denke, die Spezifikation ist noch nicht zu 100% stabil (es gibt zum Beispiel noch 3 nicht zugewiesene Befehle). Sobald ich das Gefühl habe, dass es stabiler ist, füge ich es sowohl Esolangs als auch unserem Meta-Post hinzu.
Martin Ender
Unter dem erweiterten Sechseck wird es zur äußersten linken Ecke (der 1) umgebrochen . Was 1redest du da?
mbomb007
@ mbomb007 behoben. Das war )mal ein 1.
Martin Ender
5
+1 nur für den Detaillierungsgrad in Ihrer Erklärung, wie es funktioniert. Wenn mehr Sprachen mit einem Beispiel kommen, das detailliertere
Informationen enthält, können
66

Pyth, 4 Bytes

}QPQ

Druckt Trueoder False.

orlp
quelle
12
Ich weiß, dass das alt ist, aber jetzt kannst du das auch so machen: P_Q und 1 Byte speichern.
Drobilc
14
Es ist jetzt möglich mitP_
Blue
3
@drobilc Sie können das Q ausschneiden, wenn die Funktion ein Argument erwartet, verwendet sie die Eingabe
Stan Strum
55

Netzhaut , 16 Bytes

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

Probieren Sie es online!

Beginnen wir mit einem Klassiker: Primzahlen mit einem regulären Ausdruck erkennen . Die Eingabe sollte unär sein , wobei jedes wiederholte druckbare Zeichen verwendet wird. Die Testsuite enthält eine Konvertierung von dezimal nach unär.

Ein Retina-Programm, das aus einer einzelnen Zeile besteht, behandelt diese Zeile als regulären Ausdruck und gibt die Anzahl der in der Eingabe gefundenen Übereinstimmungen aus, die 0für zusammengesetzte Zahlen und 1für Primzahlen gelten.

Der Lookahead stellt sicher, dass die Eingabe nicht zusammengesetzt ist: Bei der Rückverfolgung wird jede mögliche Teilzeichenfolge (mit mindestens 2 Zeichen) (..+)überprüft. Der Lookahead versucht dann, den Rest der Eingabe abzugleichen, indem wiederholt wird, was hier erfasst wurde. Wenn dies möglich ist, bedeutet dies, dass der Eingang einen Divisor hat, der größer als 1 ist, jedoch kleiner als er selbst ist. Wenn dies der Fall ist, schlägt der negative Lookahead die Übereinstimmung fehl. Für Primzahlen gibt es keine solche Möglichkeit und das Match geht weiter.

Das einzige Problem ist, dass dieser Lookahead dies ebenfalls akzeptiert. Daher schließen 1wir dies aus, indem wir mindestens zwei Zeichen mit übereinstimmen ...

Martin Ender
quelle
Das ist eigentlich ein unregelmäßiger Ausdruck, da die Primzahlen keine reguläre Sprache bilden.
PyRulez
@PyRulez Die meisten Regex-Aromen der realen Welt sind viel leistungsfähiger als das theoretische Konzept regulärer Ausdrücke. Ich habe den Wortlaut allerdings verbessert.
Martin Ender
1
Die derzeit leistungsstärksten "Regex" -Motoren im Freien haben eine Erkennungsleistung, die der eines linear begrenzten Automaten entspricht. Regex für Standardausgaben, Musterrekursion, unbegrenzter Lookhead und unbegrenzter Lookbehind sind alles, was Sie für das kontextsensitive Parsen benötigen (obwohl Rückverweise und dergleichen im Allgemeinen bei der Komplexisierung eines effizienten Parsings hilfreich sind), und einige haben sie alle. Lassen Sie mich nicht einmal mit den Engines beginnen, mit denen Sie Code in den regulären Ausdruck einbetten können.
eaglgenes101
52

CJam, 4 Bytes

qimp

CJam verfügt über einen eingebauten Operator zum Testen der Primalität.

Peter Taylor
quelle
18
Alternativ:limp
Sp3000
43
pimpmeine cjam.
Fehler
12
pimpist objektiv mehr Zuhälter
MickLH
1
Sie können auch tunl~mp
Kühe quaken
12
@Cyoce, qliest eine Eingabezeile, ianalysiert sie als Ganzzahl und mpist das eingebaute Element . CJam hat zwei Gruppen mit zwei eingebauten Zeichen: die "erweiterten" beginnen eund die "mathematischen" beginnenm
Peter Taylor
47

HTML + CSS, 254 + n max * 28 Bytes

Wir können die Primalität mit regulären Ausdrücken überprüfen. Mozilla hat @document, was definiert ist als:

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

Elemente über CSS basierend auf der aktuellen URL filtern. Dies ist ein einzelner Durchgang, also müssen wir zwei Schritte ausführen:

  1. Holen Sie sich eine Eingabe vom Benutzer. Diese Eingabe muss sich irgendwie in der aktuellen URL widerspiegeln.
  2. Antworten Sie dem Benutzer mit möglichst wenig Code.

1. Input bekommen

Der kürzeste Weg, um Eingaben zu erhalten und diese auf die URL zu übertragen, ist ein GETFormular mit Kontrollkästchen. Für den regulären Ausdruck benötigen wir nur eine eindeutige Zeichenfolge, um die Auftritte zu zählen.

Also fangen wir damit an (61 Bytes):

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

Wir haben zwei eindeutige <p>s, um anzuzeigen, ob die eingegebene Zahl eine Primzahl ist (1) oder nicht (0). Wir definieren auch die Form und ihre Aktion.

Gefolgt von n max Kontrollkästchen mit demselben Namen (n max * 28 Bytes):

<input type=checkbox name=i>

Gefolgt vom submit-Element (34 Bytes):

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

2. Antwort anzeigen

Wir benötigen das CSS (159 Bytes), um das <p>anzuzeigende auszuwählen (1 oder 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}}

»Probiere es bei codepen.io aus (nur Firefox)

mınxomaτ
quelle
12
+1: Dies ist mein absoluter Lieblingsmissbrauch von HTML und die Art von Dingen, die mich dazu bringen, Codegolf zu lieben.
Katze
Das ist sicherlich interessant, aber ich bin mir nicht sicher, ob es die Regeln dieser Herausforderung erfüllt. Insbesondere glaube ich nicht, dass es mit Ihrem Algorithmus übereinstimmt, [...] der theoretisch für beliebig große ganze Zahlen funktionieren sollte. Könnten Sie nicht auch einen regulären Ausdruck für den Wert eines Eingabefelds verwenden?
Dennis
@ Tennis Vielleicht. Wahrscheinlich sogar. Aber das würde das von Ihnen angesprochene Problem nicht lösen. Ich lasse es hier als nicht konkurrierenden Eintrag, weil dies die thematisch größte Herausforderung dafür ist.
Mittwoch,
Warum nicht? Wenn Sie in einem Eingabefeld eine unäre Zahl haben, hängt Ihr Code nicht mehr von der maximalen Anzahl ab.
Dennis
4
Hm, ich habe ein bisschen mehr darüber nachgedacht, und es gibt wirklich keinen Unterschied zwischen nur x Kontrollkästchen und einem Interpreter, der nur y-Bit-Zahlen hat. Ignoriere meinen vorherigen Kommentar.
Dennis
45

Hilfe, WarDoq! 1 Byte

P

Gibt 1 aus, wenn der Eingang prim ist, sonst 0.

orlp
quelle
40

Hexagony , 28 Bytes

Da mich Etoplay bei dieser Frage absolut auf die Palme brachte , hatte ich das Gefühl, dass ich seine einzige andere Antwort übertreffen musste .

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

Probieren Sie es online!

Ich verwende den Satz von Wilson, wie Martin es in seiner Antwort getan hat : Gegeben n, ich gebe aus(n-1!)² mod n

Hier hat sich das Programm entfaltet:

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

Und hier ist die lesbare Version:

Sehr gut lesbar

Erläuterung:

Das Programm besteht aus drei Hauptschritten: Initialisierung , Faktoriell und Ausgabe .

Das Speichermodell von Hexagony ist ein unendliches hexagonales Gitter. Ich benutze 5 Speicherplätze, wie in diesem Diagramm gezeigt:

Erinnerung

Ich werde auf diese Speicherorte (und die darin gespeicherten Ganzzahlen) durch ihre Bezeichnungen in diesem Diagramm verweisen.

Initialisierung:

Initialisierung

Der Anweisungszeiger ( IP ) beginnt in der oberen linken Ecke und geht nach Osten. Der Speicherzeiger ( MP ) beginnt bei IN .

Zuerst ?liest die Anzahl von Ein- und speichert sie in IN . Die IP bleibt auf dem blauen Pfad, reflektiert von \. Die Sequenz "&(bewegt den MP zurück und nach links (nach A ), kopiert den Wert von IN nach A und dekrementiert ihn.

Die IP verlässt dann eine Seite des Sechsecks und tritt wieder in die andere Seite ein (auf den grünen Pfad). Es wird ausgeführt, '+was den MP nach B verschiebt und kopiert, was in A war . <Leitet die IP nach Westen um.

Fakultät:

Ich berechne die Fakultät auf eine bestimmte Weise, so dass es einfach ist, sie zu quadrieren. Ich speichere n-1!sowohl in B als auch in C wie folgt.

Fakultät

Der Anweisungszeiger beginnt auf dem blauen Pfad in Richtung Osten.

='kehrt die Richtung des MP und bewegt ihn nach hinten zu C . Dies ist gleichbedeutend {=mit dem, =wo es später hilfreich war.

&{Kopien von dem Wert A bis C , bewegt dann den MP zurück A . Die IP folgt dann dem grünen Pfad und unternimmt nichts, bevor sie den roten Pfad erreicht \und auf den orangefarbenen Pfad trifft .

Mit (>dekrementieren wir A und leiten die IP East um. Hier trifft es eine Branche aus : <. Für positives A folgen wir dem orangen Pfad. Andernfalls wird die IP nach Nordosten gerichtet.

'*bewegt den MP zu B und speichert A * C in B . Hier war (n-1)*(n-2)die anfängliche Eingabe n. Die IP tritt dann in die Anfangsschleife zurück und setzt das Dekrementieren und Multiplizieren fort, bis A erreicht ist 0. (Computing n-1!)

NB : &Speichert bei folgenden Schleifen den Wert von B in C , da in C jetzt ein positiver Wert gespeichert ist. Dies ist für die Fakultät der Berechnung von entscheidender Bedeutung.

Ausgabe:

Ausgabe

Wenn A erreicht 0. Die Verzweigung leitet die IP stattdessen entlang des blauen Pfads.

=*die umkehrt MP und speichert den Wert von B * C in A . Dann verlässt die IP das Sechseck und tritt wieder in den grünen Pfad ein. ausführen "%. Dies bewegt den MP nach OUT und berechnet A mod IN oder (n-1!)² mod n.

Das Folgende {"wirkt wie ein No-Op, da sie sich gegenseitig aufheben. !druckt die endgültige Ausgabe und *+'(werden vor der Beendigung ausgeführt: @.

Nach der Ausführung (mit einer Eingabe von 5) sieht der Speicher folgendermaßen aus:

Memory2

Die schönen Bilder des Kontrollflusses wurden mit Timwis Hexagony Coloror aufgenommen .

Vielen Dank an Martin Ender für das Generieren aller Bilder, da ich es auf meinem PC nicht konnte.

H.PWiz
quelle
Was verwenden Sie für diese Speicherdiagramme? Ich habe Esoteric IDE gesehen, aber ich konnte es nicht zum Laufen bringen ...
NieDzejkob
@NieDzejkob frag lieber Martin im Chat, da er sie sowieso für mich gemacht hat.
H.PWiz
@NieDzejkob Ja, das Speicherdiagramm kann aus EsoIDE exportiert werden. chat.stackexchange.com/rooms/27364/… wenn Sie darüber noch mehr chatten möchten.
Martin Ender
33

Mornington Crescent , 2448 Bytes

Wir sind zurück in London!

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

Timwi war so freundlich, die Kontrollflussstationen Templeund Angelin Esoteric IDE zu implementieren und der Sprachspezifikation Eingabe- und Ganzzahlanalyse hinzuzufügen.

Dieser ist wahrscheinlich besser als der "Hallo, Welt!", Weil ich dieses Mal ein CJam-Skript geschrieben habe, um den kürzesten Weg zwischen zwei Stationen zu finden. Wenn Sie es verwenden möchten (obwohl ich nicht weiß, warum jemand es möchte ...), können Sie den Online-Dolmetscher verwenden . Füge diesen Code ein:

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

Hier sind die ersten beiden Zeilen die Stationen, die Sie überprüfen möchten. Fügen Sie außerdem den Inhalt dieses Pastebins in das Eingabefenster ein.

Die Ausgabe zeigt Ihnen, welche Leitungen an den beiden Stationen verfügbar sind, und dann eine Liste aller Stationen, die die beiden verbinden, sortiert nach der Länge der Stationsnamen. Es werden alle angezeigt, weil es manchmal besser ist, einen längeren Namen zu verwenden, weil entweder eine kürzere Linie zulässig ist oder weil die Station speziell ist (wie Bank oder Temple), damit Sie sie vermeiden möchten. Es gibt einige Randfälle, in denen zwei Stationen nicht durch eine einzige andere Station verbunden sind (insbesondere die Metropolitan- und District-Linien kreuzen sich nie). In diesem Fall müssen Sie etwas anderes herausfinden. ;)

Der eigentliche MC-Code basiert auf dem Quadratfaktor-Ansatz, ebenso wie viele andere Antworten, da MC über Multiplikation, Division und Modulo verfügt. Ich dachte mir auch, dass eine einzelne Schleife praktisch wäre.

Ein Problem ist, dass die Schleifen Do-While-Schleifen sind und das Dekrementieren und Inkrementieren teuer ist, sodass ich (n-1)!(für n > 0) nicht einfach berechnen kann . Stattdessen rechne ich n!und teile dann nam Ende durch. Ich bin sicher, dass es dafür eine bessere Lösung gibt.

Als ich anfing, dies zu schreiben, fand ich, dass das Speichern -1in Hammersmith eine gute Idee wäre, damit ich billiger sparen kann, aber am Ende hat dies möglicherweise mehr gekostet als gespart. Wenn ich die Geduld finde, dies zu wiederholen, kann ich versuchen, -1stattdessen nur in Upminster zu bleiben, damit ich Hammersmith für etwas Nützlicheres verwenden kann.

Martin Ender
quelle
10
Ist London fertig?
Rohan Jhunjhunwala
1
@ RohanJhunjhunwala wahrscheinlich
Martin Ender
Beeindruckend! Ich liebe es, gut durchdachte Fragen zu sehen. Ich sehe besonders gerne Fragen, bei denen man ein Programm schreiben muss, um ein Programm zu schreiben.
Rohan Jhunjhunwala
27

Brachylog (V2), 1 Byte

ṗ

Probieren Sie es online!

Brachylog (V1), 2 Bytes

#p

Hierbei wird das integrierte Prädikat verwendet #p - Prime, wodurch die Eingabe auf eine Primzahl beschränkt wird.

Brachylog ist mein Versuch, eine Code-Golf-Version von Prolog zu erstellen, einer deklarativen Code-Golf-Sprache, die Backtracking und Unification verwendet.

Alternative Lösung ohne eingebaute: 14 Bytes

ybbrb'(e:?r%0)

Hier ist eine Aufschlüsselung des obigen Codes:

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
)
Tödlich
quelle
1
Möglicherweise möchten Sie die Brachylog 2-Version auch in den Beitrag einfügen, da die Syntax jetzt ein Byte kürzer ist.
1
@ ais523 Richtig, fertig.
Fatalize
Beantwortet der Brachylog 2 die Herausforderung nach dem Datum?
Scott Milner
1
@ScottMilner Ja, aber dies ist in dieser Herausforderung ausdrücklich erlaubt: "Im Gegensatz zu unseren üblichen Regeln können Sie eine Sprache (oder Sprachversion) auch dann verwenden, wenn sie neuer als diese Herausforderung ist"
Fatalize
26

Haskell, 49 Bytes

Verwendung von xnors Folgerung zu Wilsons Theorem :

main=do n<-readLn;print$mod(product[1..n-1]^2)n>0
Lynn
quelle
Wäre es nicht kürzer zu tun main=interact$\n-> ...?
John Dvorak
2
Intuitiv nein! Bedenken Sie, dass Sie interact...readirgendwo drin brauchen , was es viel länger macht als nur readLn. Oft dokann die Notation prägnanter sein als erwartet, insbesondere wenn die Alternative ein Lambda ist.
Lynn
24

Labyrinth , 29 Bytes

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

Liest eine Ganzzahl aus STDIN und gibt sie aus ((n-1)!)^2 mod n. Wilsons Satz ist für diese Herausforderung ziemlich nützlich.

Das Programm beginnt in der oberen linken Ecke, beginnend mit 1dem 10-fachen des oberen Stapels und dem 1-fachen. Auf diese Weise werden in Labyrinth große Zahlen gebildet. Da die Stapel in Labyrinth jedoch mit Nullen gefüllt sind, ist der Endeffekt wie bei uns habe gerade eine 1 gedrückt.

?liest dann naus STDIN und :dupliziert es. }wechselt nzum Hilfsstapel, der am Ende für das Modulo verwendet wird. (Dann wird dekrementiert n, und wir sind bereit, mit der Berechnung der quadratischen Fakultät zu beginnen.

Unser zweites :(Duplikat) befindet sich an einer Kreuzung, und hier kommen die Kontrollflussfunktionen von Labyrinth ins Spiel. An einer Kreuzung, nachdem ein Befehl ausgeführt wurde, biegen wir nach rechts ab, wenn die Spitze des Stapels positiv ist, nach links ab und nach null fahren wir geradeaus. Wenn Sie versuchen, sich zu drehen, aber gegen eine Wand stoßen, lässt Labyrinth Sie stattdessen in die andere Richtung drehen.

Denn n = 1da die Spitze des Stapels ndekrementiert ist 0, gehen wir geradeaus. Wir haben dann einen No-Op getroffen, 'gefolgt von einem weiteren Dekrement, bei (dem wir ankommen -1. Das ist negativ, also wenden wir uns nach links und führen +plus ( -1 + 0 = -1) aus, {um nvom Hilfsstapel zum Haupt- und %Modulo ( -1 % 1 = 0) zurückzukehren. Dann geben wir mit aus !und beenden mit @.

Denn n > 1beim zweiten :biegen wir rechts ab. Wir verschieben dann }unseren kopierten Schleifenzähler auf den Hilfsstapel, duplizieren :und multiplizieren ihn zweimal **, bevor wir den Zähler zurückschieben {und dekrementieren (. Wenn wir uns immer noch sicher sind, versuchen wir, nach rechts abzubiegen, können es aber nicht. Labyrinth lässt uns stattdessen nach links abbiegen und setzt die Schleife fort. Ansonsten ist die Spitze des Stapels unser Schleifenzähler, der auf 0 reduziert wurde und den wir +zu unserem berechneten addieren ((n-1)!)^2. Schließlich verschieben wir uns nmit {dann modulo zurück %, geben aus !und beenden @.

Ich sagte, das 'ist ein No-Op, aber es kann auch zum Debuggen verwendet werden. Laufen Sie mit der -dFlagge, um den Status des Stapels jedes Mal zu sehen, wenn der 'übergangen wird!

Sp3000
quelle
2
Die Fakultät zu quadrieren ist ein wirklich cooler Trick :)
Lynn
@ Mauris Danke! Ich muss allerdings gutschreiben, wo es fällig ist - ich habe den von xnor hier
Sp3000
5
Ja, die erste Labyrinth-Antwort, die ich nicht geschrieben habe! :)
Martin Ender
24

Bash + GNU-Dienstprogramme, 16

  • 4 Bytes gespart dank @Dennis

  • 2 Bytes gespart dank @Lekensteyn

factor|awk NF==2

Die Eingabe erfolgt in einer Zeile von STDIN. Die Ausgabe ist eine leere Zeichenfolge für Falsey und eine nicht leere Zeichenfolge für Truthy. Z.B:

$ ./pr.sh <<< 1
$ ./pr.sh <<< 2
2: 2
$ ./pr.sh <<< 3
3: 3
$ ./pr.sh <<< 4
$
Digitales Trauma
quelle
2
Cool, habe von einem anderen Coreutil erfahren. Sie können zwei Zeichen factor|awk NF==2
entfernen,
@Lekensteyn - danke - aus irgendeinem Grund habe ich deinen Kommentar schon verpasst :)
Digitales Trauma
Ich würde etwas Ähnliches posten, nur länger und ohne AWK. Schön gemacht.
David Conrad
21

Java, 126 121 Bytes

Ich denke, wir brauchen eine Java-Antwort für den Anzeiger ... also hier ist eine einfache Testteilungsschleife:

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

Wie bei Java üblich, ist dies aufgrund der "Vollprogramm" -Anforderung viel größer als bei einer Funktion, was hauptsächlich auf die mainSignatur zurückzuführen ist.

In erweiterter Form:

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: Von Peter in Kommentaren korrigiert und korrigiert. Vielen Dank!

Geobits
quelle
Buggy: Es wird berichtet, dass 1das Prime ist. Sonst würde ein 4-char rettend sein , indem pund sagenfor(;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);}}arbeitet
Peter Taylor
6
Wenn Sie Zeile 3 in "long i = 2, n = Long.valueOf (a [0])" ändern, wird die Länge nicht geändert, sondern der Bereich der gültigen Eingaben erweitert.
James K Polk
4
Anstelle von können .valueOfSie new, wie in new Short(a[0]), oder verwenden new Long(a[0]), was etwas kürzer ist.
ECS
3
Sie können 4 Bytes sparen, indem Sie eine Schnittstelle verwenden und den publicModifikator löschen.
RamenChef
18

Brain-Flak , 112 108 Bytes

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

Probieren Sie es online!

Wie es funktioniert

Anfangs enthält der erste Stapel eine positive ganze Zahl n , der zweite Stapel ist leer.

Wir beginnen damit, n wie folgt zu dekrementieren .

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

n = 1

Wenn n = 1 ist Null, die while-Schleife

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

wird komplett übersprungen. Schließlich wird der verbleibende Code ausgeführt.

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

Wenn n - 1 nicht Null ist, geben wir die Schleife ein, die n = 1 überspringt. Es ist keine "echte" Schleife; Der Code wird nur einmal ausgeführt. Es wird folgendes erreicht.

{                   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 wird mit dem 42-Byte-Modul-Algorithmus aus meiner Antwort auf den Teilbarkeitstest berechnet .

Schließlich interpretieren wir die Ergebnisse, um die Primalität von n zu bestimmen .

<>    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
quelle
2
Sie müssen nicht die letzte 0 auf dem Stapel platzieren, da die wahrheitsgemäße 1 oben ausreicht. Sie können auf diese Weise zwei Bytes sparen, indem Sie das letzte entfernen {}.
Steven H.
1
Hm, ich bin hin und her gerissen. Einerseits sagt die Frage , die Ausgabe nur eines truthy oder falsy Wert bestehen sollte und 1 0ist zwei Werte. Auf der anderen Seite würden wir Arrays akzeptieren, solange die Sprache sie für wahr oder falsch hält und mehrere Stapelelemente das nächste sind, was Brain-Flak zu Arrays hat. Könnte es wert sein, dies zu Meta zu nehmen.
Dennis
Ich habe mit dem Schöpfer von Brain-Flak verifiziert, dass dies 1 0wahr ist. chat.stackexchange.com/transcript/message/32746241#32746241
Steven H.
3
Relevante Metadiskussion
Dennis
17

R, 37 29 Bytes

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

Verwendet die Probeabteilung. scan()Liest eine Ganzzahl von STDIN und cat()schreibt nach STDOUT.

Wir erzeugen einen Längenvektor n, der aus den ganzen Zahlen 1 bis nModulo besteht n. Wir testen, ob jeder !Wert 0 ist, indem wir ( ) negieren , was einen logischen Wert zurückgibt, der wahr ist, wenn die Zahl 0 ist, und falsch, wenn sie größer als 0 ist. Die Summe eines logischen Vektors ist die Anzahl der wahren Elemente, und für Primzahlen erwarten wir Die einzigen von Null verschiedenen Module sind 1 und ndaher erwarten wir, dass die Summe 2 ist.

8 Bytes gespart dank flodel!

Alex A.
quelle
Mit f=function(x)sum(!x%%1:x)==2können Sie es in 28 Bytes tun.
Mutador
2
@ AndréMuta Für diese Herausforderung müssen alle Einsendungen vollständige Programme sein und nicht nur Funktionen. Vielen Dank für den Vorschlag.
Alex A.
17

TI-BASIC, 12 Bytes

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

Ziemlich einfach. randIntNoRep(gibt eine zufällige Permutation aller ganzen Zahlen von 1 bis Ans.

Dies verbiegt die Regeln ein wenig; weil Listen in TI-BASIC auf 999 Elemente beschränkt sind, die ich interpretiert habe

Nehmen Sie an, dass die Eingabe in Ihrem Datentyp gespeichert werden kann

Dies bedeutet, dass davon ausgegangen werden kann, dass alle Datentypen für die Eingabe geeignet sind. OP stimmt dieser Interpretation zu.

Eine 17-Byte-Lösung, die tatsächlich bis zu 10 ^ 12 oder so funktioniert:

2=Σ(not(fPart(Ans/A)),A,1,Ans
Lirtosiast
quelle
@toothbrush TI-BASIC ist eine Token- Sprache, daher besteht jedes Token hier aus einem Byte, mit Ausnahme von randIntNoRep(zwei.
Lirtosiast
+1 Ah, ich habe TL-BASIC noch nie gesehen. Vielen Dank für Ihre Nachricht
Zahnbürste
1
Obwohl, es ist ein bisschen unfair, nicht wahr ...? Ich sollte eine Golfsprache schreiben, die nur 1-4 Bytes benötigt (die Frage-ID) und dann die Parameter. Es wählt die beste Antwort in einer Sprache aus, die es versteht, führt sie aus (übergibt alle Parameter) und gibt das Ergebnis zurück ... Ich frage mich, ob das gegen die Regeln verstößt. :-)
Zahnbürste
@toothbrush Zur Verteidigung von TI-BASIC: Für den Interpreter ist es nicht unfairer als die Ein-Zeichen-Befehle von Pyth und CJam, und TI-BASIC ist besser lesbar.
Lirtosiast
1
Wahr. Ich mag solche Sprachen nicht, da Lösungen in fast jeder anderen Sprache länger sind ... obwohl ich kürzlich CJam mit VB6 besiegt habe ! : -]
Zahnbürste
15

PARI / GP, 21 Bytes

print(isprime(input))

Funktioniert für lächerlich große Inputs, denn genau dafür ist PARI / GP gemacht.

Lynn
quelle
6
isprimeFührt einen APR-CL-Primalitätsnachweis durch und verlangsamt sich daher erheblich, wenn die Eingaben sehr groß werden. ispseudoprime(input)führt einen AES BPSW Probable Prime Test durch, der für über 100 Stellen viel schneller ist. Noch keine bekannten Gegenbeispiele nach 35 Jahren. Version 2.1 und frühere Versionen von Pari aus der Zeit vor 2002 verwenden eine andere Methode, die leicht zu falschen Ergebnissen führen kann, aber das sollte niemand verwenden.
DanaJ
15

TI-BASIC, 24 Byte

Beachten Sie, dass TI-Basic-Programme ein Tokensystem verwenden, sodass das Zählen von Zeichen nicht den tatsächlichen Bytewert des Programms zurückgibt.

Die Antwort von Thomas Kwa ist positiv , sie ist überlegen.

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

Stichprobe:

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

Gibt jetzt zurück, 0wenn keine Primzahl vorhanden ist oder 1wenn dies der Fall ist.

Zenohm
quelle
3
Ist die Quadratwurzel nicht nur eine Optimierung, die Sie nicht benötigen, um das Programm korrekt auszuführen?
Martin Ender
Warum müssten Sie durch zwei teilen?
Geobits
Ich liebe TI-BASIC-Antworten immer.
Grant Miller
15

Stapel Katzen , 62 + 4 = 66 Bytes

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

Muss mit den -lnBefehlszeilen-Flags ausgeführt werden (daher +4 Byte). Druckt 0für zusammengesetzte Zahlen und 1für Primzahlen.

Probieren Sie es online!

Ich denke, dies ist das erste nicht triviale Stack Cats-Programm.

Erläuterung

Eine kurze Einführung in Stack Cats:

  • Stack Cats verarbeitet eine unendliche Anzahl von Stapeln, wobei ein Bandkopf auf einen aktuellen Stapel zeigt. Jeder Stapel ist anfangs mit unendlich vielen Nullen gefüllt. Ich werde diese Nullen in meinem Wortlaut im Allgemeinen ignorieren. Wenn ich also "das Ende des Stapels" sage, meine ich den niedrigsten Wert ungleich Null, und wenn ich sage, dass "der Stapel leer ist", meine ich, dass nur Nullen darauf sind.
  • Bevor das Programm startet, -1wird a auf den Anfangsstapel geschoben, und dann wird die gesamte Eingabe darüber geschoben. In diesem Fall wird -ndie Eingabe aufgrund des Flags als dezimale Ganzzahl gelesen.
  • Am Ende des Programms wird der aktuelle Stapel für die Ausgabe verwendet. Wenn -1unten ein steht, wird es ignoriert. Aufgrund des -nFlags werden die Werte aus dem Stapel einfach als durch Zeilenvorschub getrennte Dezimalzahlen gedruckt.
  • Stack Cats ist eine umkehrbare Programmiersprache: Jeder Code kann rückgängig gemacht werden (ohne dass Stack Cats einen expliziten Verlauf verfolgt). Genauer gesagt, um einen Code umzukehren, spiegeln Sie ihn einfach, z . B. <<(\-_)wird (_-/)>>. Dieses Entwurfsziel schränkt ziemlich stark ein, welche Arten von Operatoren und Steuerungsflusskonstrukten in der Sprache existieren und welche Arten von Funktionen für den globalen Speicherstatus berechnet werden können.

  • Um das Ganze abzurunden, muss jedes Stack Cats-Programm selbstsymmetrisch sein. Möglicherweise stellen Sie fest, dass dies für den obigen Quellcode nicht der Fall ist. Das ist, wofür das -lFlag ist: Es spiegelt implizit den Code auf der linken Seite, wobei das erste Zeichen für die Mitte verwendet wird. Daher ist das eigentliche Programm:

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

Effektiv mit dem gesamten Code zu programmieren ist höchst nicht trivial und nicht intuitiv und hat noch nicht wirklich herausgefunden, wie ein Mensch es möglicherweise tun kann. Wir haben ein solches Programm brutal für einfachere Aufgaben gezwungen , wären aber nicht in der Lage gewesen, dies von Hand zu erreichen. Zum Glück haben wir ein Grundmuster gefunden, mit dem Sie eine Hälfte des Programms ignorieren können. Dies ist sicherlich nicht optimal, aber derzeit die einzige bekannte Methode, um in Stack Cats effektiv zu programmieren.

In dieser Antwort lautet die Vorlage des Musters also wie folgt (es gibt einige Unterschiede in der Art und Weise, wie es ausgeführt wird):

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

Wenn das Programm startet, sieht das Stapelband folgendermaßen aus (zum Beispiel für die Eingabe 4):

     4    
... -1 ...
     0
     ^

Der [bewegt die Oberseite des Stapels nach links (und den Bandkopf entlang) - wir nennen dies "Pushing". Und das <bewegt den Tonkopf alleine. Nach den ersten beiden Befehlen haben wir folgende Situation:

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

Nun (...)ist die eine Schleife, die ganz einfach als Bedingung verwendet werden kann: Die Schleife wird nur betreten und verlassen, wenn die Oberseite des aktuellen Stapels positiv ist. Da es momentan null ist, überspringen wir die gesamte erste Hälfte des Programms. Jetzt ist der mittlere Befehl *. Dies ist einfach XOR 1, dh es schaltet das niedrigstwertige Bit oben auf dem Stapel um und verwandelt in diesem Fall das 0in ein 1:

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

Nun begegnen wir dem Spiegelbild der (...). Dieses Mal ist die Oberseite des Stapels ist positiv und wir tun den Code eingeben. Bevor wir uns ansehen, was in den Klammern vor sich geht, lassen Sie mich erklären, wie wir am Ende abschließen: Wir möchten sicherstellen, dass am Ende dieses Blocks der Bandkopf wieder einen positiven Wert aufweist (so dass die Die Schleife endet nach einer einzelnen Iteration und wird einfach als lineare Bedingung verwendet.) Der Stapel rechts enthält die Ausgabe und der Stapel rechts davon enthält a -1. Wenn dies der Fall ist, verlassen wir die Schleife, >bewegen uns auf den Ausgabewert und verschieben ]ihn auf den, -1so dass wir einen sauberen Stapel für die Ausgabe haben.

Das ist das. Jetzt können wir in den Klammern tun, was immer wir wollen, um die Primalität zu überprüfen, solange wir sicherstellen, dass wir die Dinge wie im vorherigen Abschnitt am Ende beschrieben einrichten (was leicht mit etwas Schieben und Bewegen des Bandkopfs erledigt werden kann). Ich habe zuerst versucht, das Problem mit Wilsons Theorem zu lösen, bin aber zu weit über 100 Bytes gekommen, weil die Berechnung der faktoriellen Quadrate in Stack Cats eigentlich ziemlich teuer ist (zumindest habe ich keinen kurzen Weg gefunden). Also ging ich stattdessen zur Probedivision und das stellte sich tatsächlich als viel einfacher heraus. Schauen wir uns das erste lineare Bit an:

>:^]

Sie haben bereits zwei dieser Befehle gesehen. Außerdem :tauscht die oberen zwei Werte des aktuellen Stapels und ^XORs den zweiten Wert in den Spitzenwert. Dies :^ergibt ein allgemeines Muster, um einen Wert auf einem leeren Stapel zu duplizieren (wir ziehen eine Null über den Wert und wandeln die Null in um 0 XOR x = x). Danach sieht unser Band so aus:

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

Der von mir implementierte Trial-Division-Algorithmus funktioniert nicht für Eingaben 1, daher sollten wir den Code in diesem Fall überspringen. Wir können leicht Karte 1auf 0und alles andere auf positive Werte mit *, so ist hier, wie wir das tun:

*(*...)

Das heißt, wir verwandeln uns 1in 0, überspringen einen großen Teil des Codes, wenn wir ihn tatsächlich erhalten 0, aber innerhalb machen wir den Code sofort rückgängig, *damit wir unseren Eingabewert zurückbekommen. Wir müssen nur noch einmal sicherstellen, dass wir am Ende der Klammern mit einem positiven Wert enden, damit sie keine Schleife bilden. Innerhalb der Bedingung bewegen wir einen Stapel nach rechts >und starten dann die Hauptversuchs-Teilungsschleife:

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

Klammern (im Gegensatz zu Klammern) definieren eine andere Art von Schleife: Es handelt sich um eine Do-While-Schleife, dh, sie wird immer für mindestens eine Iteration ausgeführt. Der andere Unterschied ist die Abbruchbedingung: Bei der Eingabe der Schleife merkt sich Stack Cat den Höchstwert des aktuellen Stacks ( 0in unserem Fall). Die Schleife wird dann ausgeführt, bis derselbe Wert am Ende einer Iteration wieder angezeigt wird. Das ist für uns praktisch: In jeder Iteration berechnen wir einfach den Rest des nächsten potenziellen Divisors und verschieben ihn auf diesen Stapel, mit dem wir die Schleife beginnen. Wenn wir einen Divisor finden, ist der Rest 0und die Schleife stoppt. Wir werden versuchen, Divisoren ab n-1und dann bis zu dekrementieren 1. Das heißt, a) wir wissen, dass dies endet, wenn wir erreichen1spätestens dann und b) können wir feststellen, ob es sich bei der Zahl um eine Primzahl handelt oder nicht, indem wir den letzten Divisor untersuchen, den wir ausprobiert haben (wenn es sich um 1eine Primzahl handelt, ist es keine).

Lasst uns anfangen. Am Anfang gibt es einen kurzen linearen Abschnitt:

<-!<:^>[:

Sie wissen, was die meisten dieser Dinge inzwischen tun. Die neuen Befehle sind -und !. Stack Cats hat keine Inkrementierungs- oder Dekrementierungsoperatoren. Es hat jedoch -(Negation, dh Multiplikation mit -1) und !(bitweise NICHT, dh Multiplikation mit -1und Dekrementierung). Diese können entweder zu einem Inkrement !-oder einem Dekrement kombiniert werden -!. Also dekrementieren wir die Kopie von noben auf -1, machen dann eine weitere Kopie von nlinks auf dem Stapel, holen dann den neuen Testteiler und legen ihn darunter n. Bei der ersten Iteration erhalten wir also Folgendes:

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

Bei weiteren Iterationen wird der Wert 3durch den nächsten Testteiler usw. ersetzt (wobei die beiden Kopien von nan dieser Stelle immer den gleichen Wert haben).

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

Dies ist die Modulo-Berechnung. Da Schleifen bei positiven Werten enden, besteht die Idee darin, mit -ndem Trial-Divisor dzu beginnen und diesen wiederholt hinzuzufügen , bis ein positiver Wert erhalten wird. Sobald wir dies tun, subtrahieren wir das Ergebnis von dund dies gibt uns den Rest. Das Knifflige dabei ist, dass wir nicht einfach einen -nauf den Stapel legen und eine Schleife starten können, die sich addiert d: Wenn der obere Teil des Stapels negativ ist, wird die Schleife nicht betreten. Dies sind die Einschränkungen einer umkehrbaren Programmiersprache.

Um dieses Problem zu umgehen, beginnen wir noben auf dem Stapel, negieren es jedoch nur bei der ersten Iteration. Das klingt wieder einfacher, als es sich herausstellt ...

(-<)

Wenn die Oberseite des Stapels positiv ist (dh nur bei der ersten Iteration), negieren wir sie mit -. Dies können wir jedoch nicht einfach tun, (-)da wir dann die Schleife erst verlassen würden, wenn sie- zweimal angewendet wurde. Wir verschieben also eine Zelle nach links, <weil wir wissen, dass es dort einen positiven Wert gibt 1. Okay, jetzt haben wir ndie erste Iteration verlässlich negiert . Aber wir haben ein neues Problem: Der Bandkopf befindet sich jetzt bei der ersten Iteration an einer anderen Position als bei jeder anderen. Wir müssen dies konsolidieren, bevor wir weitermachen. Der nächste <bewegt den Bandkopf nach links. Die Situation bei der ersten Iteration:

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

Und in der zweiten Iteration (denken Sie daran, wir haben deinmal in -njetzt hinzugefügt ):

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

Die nächste Bedingung führt diese Pfade erneut zusammen:

(<!-)

Bei der ersten Iteration zeigt der Bandkopf auf eine Null, sodass diese vollständig übersprungen wird. Bei weiteren Iterationen zeigt der Bandkopf jedoch auf eine Eins. Führen Sie dies also aus, bewegen Sie sich nach links und erhöhen Sie die Zelle dort. Da wir wissen, dass die Zelle bei Null beginnt, ist sie jetzt immer positiv, sodass wir die Schleife verlassen können. Dies stellt sicher, dass wir immer zwei Stapel vom Hauptstapel übrig haben und jetzt mit zurückgehen können >>. Dann machen wir am Ende der Modulo-Schleife -_. Du weißt es schon -. _ist Subtraktion , was ^zu XOR ist: Wenn die Oberseite des Stapels ist aund der Wert darunter ist bes ersetzt amit b-a. Da wir zuerst negiert ajedoch -_ersetzt amit b+a, wodurch das Hinzufügend in unsere laufende Summe.

Nachdem die Schleife beendet ist (wir haben einen positiven Wert erreicht), sieht das Band folgendermaßen aus:

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

Der am weitesten links stehende Wert kann eine beliebige positive Zahl sein. In der Tat ist es die Anzahl der Iterationen minus eins. Es gibt jetzt noch ein kurzes lineares Bit:

_<<]>:]<]]

Wie ich bereits sagte, müssen wir das Ergebnis von subtrahieren d, um den tatsächlichen Rest ( 3-2 = 1 = 4 % 3) zu erhalten, also machen wir es einfach noch _einmal. Als nächstes müssen wir den Stapel bereinigen, den wir links erhöht haben: Wenn wir den nächsten Divisor versuchen, muss er wieder Null sein, damit die erste Iteration funktioniert. Also bewegen wir uns dorthin und schieben diesen positiven Wert mit auf den anderen Hilfsstapel <<]und bewegen uns dann mit einem anderen auf unseren operativen Stapel zurück >. Wir ziehen dmit :und schieben es zurück auf das -1mit ]und dann bewegen wir den Rest auf unseren bedingten Stapel mit <]]. Das ist das Ende der Testteilungsschleife: Dies wird fortgesetzt, bis wir einen Rest von Null erhalten. In diesem Fall enthält der Stapel auf der linken Seitender größte Teiler (außer n).

Nachdem die Schleife beendet ist, müssen *<wir die Pfade erst wieder mit der Eingabe verbinden 1. Das *verwandelt die Null einfach in eine 1, die wir gleich brauchen, und dann bewegen wir uns zum Divisor mit <(so dass wir uns auf dem gleichen Stapel wie für die Eingabe befinden 1).

An dieser Stelle hilft es, drei verschiedene Arten von Eingaben zu vergleichen. Erstens, der Sonderfall, n = 1in dem wir nichts von diesem Teilprozess gemacht haben:

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

Dann ist unser vorheriges Beispiel n = 4eine zusammengesetzte Zahl:

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

Und schließlich n = 3eine Primzahl:

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

Für Primzahlen haben wir also einen 1auf diesem Stapel, und für zusammengesetzte Zahlen haben wir entweder eine 0oder eine positive Zahl größer als 2. Wir machen aus dieser Situation das 0oder das, was 1wir brauchen, mit dem folgenden abschließenden Code:

]*(:)*=<*

]schiebt diesen Wert einfach nach rechts. Dann *verwendet die bedingte Situation stark zu vereinfachen: durch das niedrigstwertige Bit Makeln, wir drehen 1(prime) in 0, 0(Composite) in den positiven Wert 1, und alle anderen positiven Werte bleiben nach wie vor positiv. Jetzt müssen wir nur noch zwischen 0positiv und positiv unterscheiden. Dort setzen wir einen anderen ein (:). Wenn die Spitze des Stapels ist 0(und die Eingabe eine Primzahl war), wird dies einfach übersprungen. Aber wenn die Spitze des Stapels positiv ist (und die Eingabe eine zusammengesetzte Zahl war), wird sie durch die vertauscht 1, so dass wir nun 0für zusammengesetzte und haben1für Primzahlen - nur zwei unterschiedliche Werte. Natürlich sind sie das Gegenteil von dem, was wir ausgeben wollen, aber das kann leicht mit einem anderen behoben werden *.

Jetzt müssen wir nur noch das von unserem umgebenden Framework erwartete Stapelmuster wiederherstellen: Bandkopf auf einen positiven Wert, Ergebnis oben rechts -1auf dem Stapel und ein einzelnes auf dem Stapel rechts davon . Dafür ist =<*. =tauscht die Oberseiten der beiden benachbarten Stapel aus und verschiebt dabei den -1nach rechts vom Ergebnis, z. B. für die 4erneute Eingabe :

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

Dann bewegen wir uns einfach nach links <und machen aus dieser Null eine Eins mit *. Und das ist das.

Wenn Sie mehr über die Funktionsweise des Programms erfahren möchten, können Sie die Debug-Optionen verwenden. Fügen Sie entweder das -dFlag hinzu und fügen "Sie es an einer beliebigen Stelle ein, an der Sie den aktuellen Speicherstatus anzeigen möchten, z. B. so , oder verwenden Sie das -DFlag , um eine vollständige Ablaufverfolgung des gesamten Programms abzurufen . Alternativ können Sie Timwis EsotericIDE verwenden, das einen Stack Cats-Interpreter mit einem schrittweisen Debugger enthält.

Martin Ender
quelle
3
>:^]sollte das offizielle Stack Cats-Logo sein
Alex A.
14

Haskell, 54 Bytes

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

Es gibt nicht viel zu erklären.

nimi
quelle
1
Dieselbe Punktzahl kann (obwohl sehr ineffizient) ohne externe Bibliotheken erreicht werden, wenn man den Satz von Wilson verwendet:main=do n<-readLn;print$n>1&&mod(product[1..n-1]+1)n<1
Lynn
9
Wir können noch kürzer machen: main=do n<-readLn;print$mod(product[1..n-1]^2)n>0ist 49 Bytes.
Lynn
4
@ Mauris: Schön. Bitte posten Sie es als separate Antwort.
nimi
14

Ruby, 15 + 8 = 23 Bytes

p$_.to_i.prime?

Probelauf:

bash-4.3$ ruby -rprime -ne 'p$_.to_i.prime?' <<< 2015
false
Mann bei der Arbeit
quelle
Heheh, ich wusste, dass irgendwo in Ruby eine eingebaute Version vorhanden sein würde, aber ich konnte nicht die Mühe haben, danach zu suchen, also antwortete ich in C + 1.
Level River St
@steveverrill, ich wusste es, weil es eine große Hilfe für Project Euler war.
Manatwork
14

JavaScript, 39 36 Bytes

Dank ETHproductions 3 Bytes gespart:

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

Zeigt true für eine Primzahl an, andernfalls false.

Die for- Schleife testet jede Zahl i von n-1 bis i ein Divisor ist. Wenn der erste gefundene Divisor 1 ist, ist es eine Primzahl.

Vorherige Lösung (39 Bytes):

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

Wie blieb ein nicht benötigter Test:

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

Ich habe nur die 39-Byte-Lösung gepostet, da die beste JavaScript-Antwort bereits 40 Byte war.

Hedi
quelle
2
Willkommen bei Programming Puzzles & Code Golf!
Dennis
2
Gute Antwort! Der &&imacht eigentlich nichts in diesem Programm, also können Sie es entfernen.
ETHproductions
sollte n>1die endgültige Bedingung jedoch ergänzen , wenn du nicht primer sein willst 1.
Titus
1
@Titus Wenn die Eingabe 1die for-Schleife ist, wird sie n%--ieinmal ausgeführt: Gibt die Schleife 1%0zurück NaNund stoppt sie. Wann gerufen alertwird iist schon gleich 0so 1==ikehrt zurück false.
Hedi
2
i <2 (und etwas Text)
Scheintod
13

Schnecken, 122

Die Eingabe sollte in unary erfolgen. Bei den Ziffern kann es sich um beliebige Zeichenmischungen handeln, mit Ausnahme von Zeilenumbrüchen.

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

In dieser 2D-Pattern-Matching-Sprache besteht der Programmstatus ausschließlich aus der aktuellen Rasterposition, der Menge der übereinstimmenden Zellen und der Position im Pattern-Code. Es ist auch illegal, auf ein gleiches Feld zu fahren. Es ist schwierig, aber es ist möglich, Informationen zu speichern und abzurufen. Die Einschränkung, in eine übereinstimmende Zelle zu gelangen, kann durch Backtracking, Teleporting ( t) und Assertions ( =, !) überwunden werden , die das Gitter nach dem Abschluss unverändert lassen.

Faktorisierung von 25

Die Faktorisierung für eine ungerade zusammengesetzte Zahl beginnt mit der Markierung eines Satzes nicht benachbarter Zellen (blau im Diagramm). Anschließend überprüft das Programm anhand jeder gelben Zelle, ob sich auf beiden Seiten der benachbarten blauen Zelle eine gleiche Anzahl von nicht blauen Zellen befindet, indem es zwischen den beiden Seiten hin und her fährt. Das Diagramm zeigt dieses Muster für eine der vier gelben Zellen, die überprüft werden müssen.

Kommentierter Code:

^                         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
quelle
13

C 67 Bytes

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

Druck !1(a Falsey Wert, von Peter Taylor Definition ) 0 , wenn (n-1)!^2 == 0 (mod n)und 1sonst.

BEARBEITEN : Nach einigen Diskussionen im Chat, puts("!1"+p%n)scheint ein bisschen betrogen zu werden, also habe ich es ersetzt. Das Ergebnis ist ein Byte länger.

BEARBEITEN : Bei großen Eingaben behoben.

Kürzere Lösungen

56 Bytes : Wie in den Kommentaren von pawel.boczarski empfohlen, könnte ich die Eingabe unärgerlich machen, indem ich die Anzahl der Befehlszeilenargumente lese:

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

Aufrufen des Programms wie

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

51 Bytes : Wenn Sie die "Ausgabe" über Returncodes erlauben:

p=1,n;main(i){for(n=--i;--i;p=p*i*i%n);return p%n;}
Lynn
quelle
Ihre Lösung könnte durch unäre Darstellung (Anzahl der Befehlszeilenargumente) kürzer gemacht werden, wie in meiner Lösung angegeben. Sie könnten einige Bytes beim Scanf-Aufruf abschneiden.
pawel.boczarski
puts("!1"+p%n)Wie könnten Sie jemals a+bfür char*Werte tun ?
Erik der Outgolfer
Wenn die Zeichenfolge "!1"an der Adresse beginnt a, a+1finden Sie die Zeichenfolge an "1".
Lynn
@Lynn Oh, ich dachte , es für Verkettung war (ja, lassen Sie besser , dass zu strcat(const char*,const char*).)
Erik die Outgolfer
Könnten Sie wechseln p=p*i*i%nzup*=i*i%n
Albert Renshaw
12

Python 3, 59 Bytes

Verwendet jetzt input()anstelle von Befehlszeilenargumenten. Vielen Dank an @Beta Decay

n=int(input())
print([i for i in range(1,n)if n%i==0]==[1])
uno20001
quelle
Nehmen Sie die Eingabe mit input()wäre viel kürzer
Beta Decay
Danke, ich habe bereits mit der Verwendung von input () geschrieben, aber ich habe vergessen, meine Antwort zu aktualisieren. Danke noch einmal!
uno20001
4
52 Bytes: n=m=int(input()),print(all(n%m for m in range(2,n)))
John Lyon
1
Sind Sie im Ernst. 25 zusätzliche Charaktere für ein lahmes quadratisches Tempo ausgeben? Hier hassen wir Bytes . Wir verbringen jede Stunde, Minute und Sekunde unseres Lebens damit, das neunzehnte Byte loszuwerden. (Nur ein Scherz. Aber wir machen keine Zeitoptimierungen, die die Programmlänge erhöhen.)
CalculatorFeline
2
Verwenden Sie n%i<1stattdessen.
Erik der Outgolfer
12

APL, 40 13 Bytes

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

Versuchsteilung mit dem gleichen Algorithmus wie meine R-Antwort . Wir ordnen xdie Eingabe von STDIN ( ⎕) zu und erhalten den Rest für xgeteilt durch jede ganze Zahl von 1 bis x. Jeder Rest wird mit 0 verglichen, was uns einen Vektor aus Einsen und Nullen gibt, der angibt, welche ganzen Zahlen sich teilen x. Dies wird mit +/der Anzahl der Teiler summiert . Wenn diese Zahl genau 2 ist, bedeutet dies, dass die einzigen Teiler 1 und xund somit xPrimzahl sind.

Alex A.
quelle
12

Metaprogrammierung von C ++ - Vorlagen. 166 131 119 Bytes.

Code wird kompiliert, wenn die Konstante eine Primzahl ist, und wird nicht kompiliert, wenn composite oder 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];

(Alle Zeilenumbrüche außer dem letzten werden in der "echten" Version entfernt).

Ich nehme an, "Fehler beim Kompilieren" ist ein falscher Rückgabewert für eine Metaprogrammiersprache. Beachten Sie, dass es nicht als vollständiges C ++ - Programm verknüpft wird (wenn Sie es also als Primzahl angeben, werden Verknüpfungsfehler angezeigt).

Der zu testende Wert ist die Ganzzahl in der letzten "Zeile".

Live-Beispiel .

Yakk
quelle