Diese Herausforderung ist so einfach, dass im Grunde alles im Titel steht: Sie erhalten eine positive ganze Zahl N und Sie sollten die kleinste positive ganze Zahl zurückgeben, die kein Teiler von N ist .
Ein Beispiel: Die Teiler von N = 24 sind 1, 2, 3, 4, 6, 8, 12, 24
. Die kleinste positive Ganzzahl, die nicht in dieser Liste enthalten ist , ist 5 , das ist also das Ergebnis, das Ihre Lösung finden sollte.
Dies ist die OEIS-Sequenz A007978 .
Regeln
Sie können ein Programm oder eine Funktion schreiben und eine unserer Standardmethoden zum Empfangen und Bereitstellen von Eingaben verwenden.
Sie können jede Programmiersprache verwenden , beachten Sie jedoch, dass diese Lücken standardmäßig verboten sind.
Das ist Code-Golf , also gewinnt die kürzeste gültige Antwort - gemessen in Bytes .
Testfälle
Die ersten 100 Begriffe sind:
2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2,
3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3,
2, 3, 2, 4, 2, 3, 2, 3, 2, 7, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2,
3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3
Stellen Sie insbesondere sicher, dass Ihre Antwort für die Eingaben 1 und 2 funktioniert. In diesem Fall ist das Ergebnis größer als die Eingabe.
Und für einige größere Testfälle:
N f(N)
1234567 2
12252240 19
232792560 23
quelle
Antworten:
Mathematica, 19 Bytes (UTF-8-Codierung)
Unbenannte Funktion, die ein Ganzzahlargument ungleich Null verwendet und eine positive Ganzzahl zurückgibt. Der vertikale Balken auf halbem Weg ist das Drei-Byte-Zeichen U + 2223, das die Teilbarkeitsrelation in Mathematica angibt. Erläuterung:
Bearbeitet, um hinzuzufügen: ngenisis weist darauf hin, dass
//.
standardmäßig maximal 65536-mal iteriert wird. Diese Implementierung funktioniert also für alle Eingabenummern, die kleiner sind als das kleinste gemeinsame Vielfache der ganzen Zahlen von 1 bis 65538 (insbesondere für alle Zahlen mit höchstens 28436 Ziffern), aber technisch nicht für alle Zahlen. Man kann ersetzenx//.y
mitReplaceRepeated[x,y,MaxIterations->∞]
diesen Fehler zu beheben, aber offensichtlich auf Kosten von 34 zusätzlichen Bytes.quelle
For
,While
usw.Pyth, 3 Bytes
f
Schleifen Sie den Code grundsätzlich, bis%QT
(Q % T
woT
ist die Iterationsvariable) wahr ist.Probieren Sie es hier online aus.
quelle
.V1In%Qb0bB
Sah deine Antwort und fühlte mich nicht mehr so großartig.JavaScript (ES6),
2523 BytesHinweis: Interessant ist hier, dass der
k
Parameter bei der ersten Iteration ex nihilo initialisiert wird. Dies funktioniert, weiln % undefined
istNaN
(falsch wie erwartet) und-~undefined
gleich1
. Bei den nächsten Iterationen-~k
entspricht im Wesentlichenk+1
.Prüfung
Code-Snippet anzeigen
quelle
Python,
433635 Bytesquelle
Hexagony , 12 Bytes
Begünstigt:
Probieren Sie es online!
quelle
R, 28 Bytes
Ziemlich unkompliziert, nichts Besonderes. Übernimmt die Eingabe von stdin und erhöht den Wert,
T
bisi
moduloT
ungleich Null ist.Wenn Sie etwas ausgefalleneres möchten, gibt es für 29 Bytes Folgendes :
Erklärt:
quelle
which.min
, aber dann sah ich die Bearbeitung und es scheint,match
macht einen ähnlichen Job.T
, erspart die Notwendigkeit, ihn vor derwhile
Schleife zu definieren .while
Ansatz, was in Ordnung ist, da er für große N sehr speicherintensiv ist. DerT
Trick ist eine dieser Leckerbissen, die für das Golfen großartig, für das eigentliche Programmieren jedoch absolut schrecklich ist. (Und natürlich können Sie auch verwenden,F
wenn Sie eine benötigen0
.)%%
Vorrang vor+
, daher sind noch Parens erforderlich:,(0:i+1)
mit der gleichen Anzahl von Bytes wie1:(i+1)
. Ersteres hatte ich ursprünglich, habe es aber durch Letzteres ersetzt, da es leichter zu lesen ist.Haskell, 26 Bytes
Jeder vergisst über
until
!quelle
Brachylog , 10 Bytes
Probieren Sie es online!
Dies war sehr ähnlich (aber kürzer als die ursprüngliche Lösung von Fatalize). Fatalize hat seitdem auf einen anderen Algorithmus umgestellt, der über eine andere Methode mit diesem verknüpft ist. Deshalb muss ich das selbst erklären:
Wenn wir die Funktion invertieren, indem wir "Eingabe" und "Ausgabe" vertauschen, erhalten wir einen ziemlich vernünftigen Algorithmus (nur auf unangenehme Weise ausgedrückt): "Probieren Sie mögliche positive ganze Zahlen in ihrer natürlichen Reihenfolge (dh 1 aufwärts) aus, bis Sie finden eine, die nicht mit irgendetwas multipliziert werden kann, um die Eingabe zu erzeugen ". Brachylog führt keine Gleitkommaberechnungen durch, es sei denn, alle Eingaben sind bekannt. Daher wird nur die Ganzzahl A berücksichtigt.
quelle
Brachylog ,
1110 BytesProbieren Sie es online!
Erläuterung
quelle
COW, 174 Bytes
Probieren Sie es online!
Dieser Code ist nur teilweise mein eigener - er implementiert einen Modulalgorithmus, den ich aus Brainfuck portiert habe. Der Rest des Codes ist mein eigener. Da ich den Modulalgorithmus jedoch nicht geschrieben habe, habe ich nicht wirklich untersucht, wie er funktioniert, und kann diesen Teil des Codes nicht dokumentieren. Stattdessen werde ich meine übliche Aufschlüsselung geben, gefolgt von einer ausführlicheren Erläuterung, warum der Code funktioniert.
Code-Aufschlüsselung
Erläuterung
Der Code liest zuerst die ganze Zahl in [0]. Jede Iteration der Hauptschleife (Zeilen 2 bis 26) inkrementiert [1] und kopiert dann alles Notwendige in den Modulalgorithmus, der das Ergebnis in [5] ausspuckt. Wenn [5] irgendeinen Wert enthält, dann ist [1] die Zahl, die wir drucken müssen. Wir drucken es und beenden dann das Programm.
Da COW ein Brainfuck-Derivat ist, funktioniert es relativ ähnlich wie Brainfuck. Sie können einen unendlichen Bandstreifen nach links oder rechts bewegen, erhöhen oder verringern und "loopen", während der aktuelle Bandwert ungleich Null ist. Zusätzlich zum Brainfuck bietet COW eine Reihe nützlicher Funktionen.
Der eigentliche Punkt von Interesse ist hier die Anweisung 3
mOO
,. Der Interpreter liest den aktuellen Bandwert und führt eine Anweisung basierend auf diesem Bandwert aus. Wenn der Wert kleiner als 0, größer als 11 oder gleich 3 ist, beendet der Interpreter das Programm. Wir können dies als schnelles und schmutziges Verlassen der Hauptschleife (und des Programms vollständig) verwenden, sobald wir unseren Nicht-Divisor gefunden haben. Alles, was wir tun müssen, ist, unsere Nummer auszudrucken, [1] (mitOOO
) zu löschen , sie mit auf -1 zu dekrementierenMOo
und dann den Befehl -1 auszuführen, übermOO
den das Programm endet.Das Band selbst für dieses Programm funktioniert wie folgt:
Der Modulalgorithmus löscht natürlich [2], [3], [6] und [7] am Ende der Operation. Der Inhalt von [4] wird mit der Registerpaste in Zeile 4 überschrieben, und [5] ist Null, wenn [0] durch [1] teilbar ist, sodass wir ihn nicht löschen müssen. Wenn [5] ungleich Null ist, beenden wir Zeile 23 zwangsweise, damit wir uns darüber keine Sorgen machen müssen.
quelle
05AB1E , 7 Bytes
Probieren Sie es online!
Erläuterung
quelle
Gelee , 5 Bytes
Probieren Sie es online!
Erläuterung:
Dies ist ein schrecklicher Missbrauch von
#
; Es gibt viele Operatoren in diesem Programm, aber eine Menge fehlender Operanden.#
möchte wirklich1
, dass das aus irgendeinem Grund explizit angegeben wird (andernfalls wird versucht, die Eingabe als Standard festzulegen); Alles andere, was nicht im Programm angegeben ist, wird standardmäßig vom Programm eingegeben. (Wenn Sie beispielsweise 24 als Eingabe eingeben, findet dieses Programm die ersten 24 Zahlen, die 24 nicht teilen, und gibt dann die erste zurück. Dies ist zwar verschwenderisch, funktioniert aber.)quelle
2%@1#
C,
3235 BytesBearbeiten:
i=1
in der Schleife hinzugefügtVerwendungszweck
Vollversion des Programms, 64 Bytes:
quelle
C #,
3937 BytesZwei Bytes gespart dank Martin!
quelle
Perl, 19 Bytes
18 Byte Code +
-p
Flag.Um es auszuführen:
Nicht sehr detaillierte Erklärungen:
-
$.
ist eine spezielle Variable, deren Standardwert die aktuelle Zeilennummer des zuletzt aufgerufenen Dateihandles ist (hier stdin). Nach dem Lesen der ersten Eingabezeile wird sie auf 1 gesetzt.-
$_
hält die Eingabe und wird implizit gedruckt am ende (dank-p
flagge).-
redo
(in diesem Zusammenhang) geht davon aus, dass sich das Programm in einer Schleife befindet, und wiederholt die aktuelle Iteration (nur$.
anders, da sie erhöht wurde).- Wenn wir also die kleinste Zahl (gespeichert in
$.
) gefunden haben, die sich nicht teilt$_
, setzen wir$_
sie auf, andernfalls versuchen wir es mit der nächsten Zahl (danke anredo
).quelle
Oktave / MATLAB,
2624 Bytesfind(...,1)
Gibt den Index (1
-basiert) des ersten Nicht-Null-Elements des Vektors im ersten Argument zurück. Das erste Argument lautet:[n mod 1, n mod 2, n mod 3, n mod 4,...,n mod (n+1)]
Das heißt, wir müssen+1
den Index erweitern, da wir mit dem Testen bei beginnen1
. Danke @ Giuseppe für -2 Bytes.Probieren Sie es online!
quelle
@(n)find(mod(n,1:n+1),1)
ist kürzer, nicht wahr?Gelee , 6 Bytes
Probieren Sie es online!
Erläuterung:
quelle
[1, 1, 1, 1, 5, ...]
.Perl 6 , 17 Bytes
Versuch es
Erweitert:
quelle
05AB1E , 6 Bytes
Probieren Sie es online!
Außerdem heißt es "LINK!" ... Ein bisschen ...
quelle
Gelee , 5 Bytes
Probieren Sie es online!
Wie es funktioniert
quelle
Python 2.7.9, 32 Bytes
Test auf Ideone
Zählt potenzielle Nicht-Teiler rekursiv auf
d
. Es ist kürzer, das Ergebnis rekursiv zu erhöhen als auszugebend
. Ein Offset von1
wird durch den Booleschen Wert von erreichtTrue
, der gleich1
ist. Dad==1
es sich jedoch immer um einen Divisor handelt, wird die Ausgabe immer in eine Zahl umgewandelt.Python 2.7.9 wird verwendet, um zuzulassen
0or
. Versionen ab 2.7.10 versuchen,0or
als Beginn einer Oktalzahl zu analysieren und erhalten einen Syntaxfehler. Sehen Sie dies auf Ideone .quelle
Eigentlich 7 Bytes
Probieren Sie es online! (Hinweis: Dies ist eine sehr langsame Lösung, die für große Testfälle viel Zeit in Anspruch nimmt.)
Erläuterung:
quelle
Haskell , 29 Bytes
Der Ausdruck
[k|k<-[2..]]
erstellt nur eine unendliche Liste[2,3,4,5,...]
. Mit der Bedingungmod n k>0
erlauben wir nur diejenigenk
in der Liste, die sich nicht teilenn
. Das Anhängen gibt!!0
nur den ersten Eintrag (den Eintrag am Index0
) aus dieser Liste zurück.Probieren Sie es online!
quelle
Dyalog APL , 8 Bytes
1⍳⍨
Position des ersten True in0≠
die Nicht-Null-Werte von⍳|
der Teilungsrest von 1 ... N bei Division durch⊢
NTryAPL online!
Hinweis: Dies funktioniert für 1 und 2, da
1⍳⍨
1 + die Länge des Arguments zurückgegeben wird, wenn keine gefunden wird.quelle
Julia, 28 Bytes
Hinweis: Da
1:N+2
kein Speicher reserviert wird, gibt es keine Speicherprobleme für großeN
s- @flawr - spart
N+2
mir einige Bytes- @Martins Vorschlag sparte 1 Bytes
quelle
QBIC , 14 Bytes
Erläuterung:
quelle
PHP, 30 Bytes
Wenn laufen von der Konsole mit
-r
Option (Danke an @ ais523)32 Bytes
danke an @manatwork für das entfernen von 1 byte
33 Bytes (original)
quelle
<?
muss nicht Teil Ihrer Byteanzahl sein (da PHP über einen Befehlszeilenmodus verfügt, der dies nicht erfordert).<1
statt==0
.for(;!($argv[1]%$i);$i++);echo$i;
. Dein ist die natürliche Entwicklung von mir. Das hat meine Zustimmung!Cubix ,
1412 Bytes2 Bytes gespart dank MickyT.
Versuch es
Erläuterung
In Würfelform lautet der Code:
Grundsätzlich übernimmt dies nur die Eingabe und startet einen Zähler. Anschließend wird jeder nachfolgende Wert des Zählers geprüft, bis ein Wert gefunden wird, der kein Faktor für die Eingabe ist.
quelle
I2/L/);?%<@O
für ein paar Bytes weniger. Gleicher allgemeiner Prozess, nur ein anderer Weg> <> , 15 +3 = 18 Bytes
Es wird erwartet, dass die Eingabe beim Programmstart auf dem Stack ist, also +3 Bytes für das
-v
Flag. Probieren Sie es online!quelle
Qualle ,
1210 BytesÜbernimmt die Eingabe von STDIN und gibt sie an STDOUT aus. Probieren Sie es online!
Martin Ender hat 2 Bytes gespart, danke!
Erläuterung
Dieser Teil ist eine Funktion, die den Eingabewert in ihrer Definition verwendet.
Diese
~
-Zelle erhält eine Funktion, also dreht sie ihre Argumente um: Sie erzeugt die Binärfunktion "linkes Argument modulo (|
) rechtes Argument". Die in Jellyfish integrierte Modulo-Funktion führt die Argumente in umgekehrter Reihenfolge aus.Diese
~
-Zelle erhält einen Wert und eine Funktion, weshalb sie teilweise angewendet wird: Sie erzeugt die Binärfunktion "input (i
) modulo right argument". Nennen wir diese Funktion f .Die
\
-Zelle erhält zwei Funktionen und führt daher eine Iteration durch: Sie erzeugt die unäre Funktion "increment (>
), bis die auf vorherige und aktuelle Werte angewendete Funktion f ein wahres Ergebnis (ungleich Null) ergibt, und gibt dann den aktuellen Wert zurück". Dies bedeutet, dass das Argument solange inkrementiert wird, bis die Eingabe nicht mehr geteilt wird.Zuletzt wenden wir diese Funktion auf den Anfangswert an
1
und drucken das Ergebnis mitp
.quelle