Definition
Eine Zahl ist positiv, wenn sie größer als Null ist.
Eine Zahl ( A
) ist der Teiler einer anderen Zahl ( B
), wenn A
sie B
ohne Rest geteilt werden kann.
Zum Beispiel 2
ist ein Teiler von 6
weil 2
kann 6
ohne Rest teilen .
Tor
Ihre Aufgabe ist es, ein Programm / eine Funktion zu schreiben, die eine positive Zahl annimmt, und dann alle ihre Teiler zu finden.
Beschränkung
- Sie dürfen keine eingebauten Elemente in Bezug auf Primzahl oder Faktorisierung verwenden .
- Die Komplexität Ihres Algorithmus darf O (sqrt (n)) nicht überschreiten .
Freiheit
- Die Ausgabeliste kann Duplikate enthalten.
- Die Ausgabeliste muss nicht sortiert werden.
Wertung
Das ist Code-Golf . Die kürzeste Lösung in Bytes gewinnt.
Testfälle
input output
1 1
2 1,2
6 1,2,3,6
9 1,3,9
code-golf
arithmetic
restricted-source
number-theory
restricted-complexity
Undichte Nonne
quelle
quelle
O(sqrt(n))
.99 (1 3 9 11 33 99)
Antworten:
PostgreSQL, 176 Bytes
SqlFiddleDemo
Eingang:
(SELECT ...v)
Wie es funktioniert:
(SELECT ...v)
- Eingabegenerate_series(1, sqrt(v)::int)
- Zahlen von 1 bis sqrt (n)WHERE v%r=0
-FilterteilerSELECT r FROM c UNION SELECT v/r FROM c
Rest der Teiler erzeugen und kombinierenSELECT string_agg(r::text,',' ORDER BY r)
das durch Kommas getrennte Endergebnis erzeugenEingabe als Tabelle:
SqlFiddleDemo
Ausgabe:
quelle
C # 6, 75 Bytes
Basierend auf der C # -Lösung von downrep_nation, jedoch rekursiv und weiter unten mit einigen neuen Funktionen von C # 6 gespielt.
Der grundlegende Algorithmus ist der gleiche wie der von downrep_nation. Die for-Schleife wird in eine Rekursion umgewandelt, also der zweite Parameter. Der Rekursionsstart erfolgt über den Standardparameter, daher wird die Funktion nur mit der erforderlichen einzelnen Startnummer aufgerufen.
Da die meisten Antworten hier (noch) nicht dem genauen Ausgabeformat aus den Beispielen folgen, behalte ich es so wie es ist, aber als Nachteil enthält die Funktion ein einzelnes nachfolgendes Komma im Ergebnis.
quelle
R ,
3631 BytesProbieren Sie es online aus!
-5 Bytes dank Robin Ryder
quelle
n^.5
stattsqrt(n)
.1
vielen Male duplizieren .Matlab, 48 Bytes
quelle
sqrt(n)
und füge dann jeden Divisord
undn/d
in meine Liste ein.b=~mod(n,a)
1 Byte speichern?J, 26 Bytes
Erläuterung
quelle
JavaScript (ES6) - 48 Bytes
Nicht sehr effizient, funktioniert aber! Beispiel unten:
quelle
MATL , 12 Bytes
Der Ansatz ähnelt dem in der Antwort von @ errorr .
Probieren Sie es online aus!
Erläuterung
quelle
05AB1E ,
1412 BytesCode:
Erläuterung:
Verwendet die CP-1252- Codierung. Probieren Sie es online aus! .
quelle
Python 2, 64 Bytes
Diese anonyme Funktion gibt eine Liste von Teilern aus. Die Teiler werden durch Versuchsteilung von ganzen Zahlen in dem Bereich berechnet
[1, ceil(sqrt(n))]
, der istO(sqrt(n))
. Wennn % x == 0
(äquivalent zun%x<1
), dann sind beidex
undn/x
Teiler vonn
.Probieren Sie es online aus
quelle
Gelee , 9 Bytes
Wie die anderen Antworten, ist dies O (√n), wenn wir die (falsche) Annahme machen, dass die ganzzahlige Division O (1) ist .
Wie es funktioniert
Probieren Sie es online aus!
quelle
Javascript, 47 Bytes
quelle
Mathematica, 50 Bytes
Ähnlich @ flawr der Lösung .
Führt eine Spurteilung für x von 1 bis zur Quadratwurzel von n durch und speichert sie, falls teilbar, in einer Liste als x und n / x .
∣
dass für die Darstellung in UTF-8 3 Byte erforderlich sind, sodass für die 48-Zeichen-Zeichenfolge in der UTF-8-Darstellung 50 Byte erforderlich sind.Verwendung
quelle
JavaScript (ES6),
6662 ByteIch dachte, ich würde eine Version schreiben, die eine sortierte deduplizierte Liste zurückgibt, und es stellte sich heraus, dass sie 4 Bytes kürzer war ...
quelle
C #, 87 Bytes
Golf gespielt
Ungolfed
Vollständiger Code
Veröffentlichungen
87 bytes
- Erste Lösung.Anmerkungen
var
's undint
' s anstelle vonString
's undInt32
' s, um den Code zu verkürzen , während ich im Ungolfed-Code und im vollständigen CodeString
's undInt32
' s verwende, um den Code lesbarer zu machen.quelle
for
ist im Allgemeinen besser alswhile
.for
Schleife die gleiche Länge wie diewhile
Schleife. In diesem Fall ist es irrelevant, ein oder das andere zu haben.Lua, 83 Bytes
Ich könnte es leider nicht besser machen
quelle
Perl 6 , 40 Bytes
Erläuterung:
Verwendung:
quelle
c #, 87 Bytes
Ich weiß nicht, ob dies für alle Zahlen funktioniert, ich vermute, dass es funktioniert.
aber die Komplexität stimmt, also ist das schon etwas, nicht wahr?
quelle
Ruby, 56 Bytes
quelle
IA-32 Maschinencode, 27 Bytes
Hexdump:
Quellcode (MS Visual Studio-Syntax):
Der erste Parameter (
ecx
) ist ein Zeiger auf die Ausgabe, der zweite Parameter (edx
) ist die Zahl. Es markiert in keiner Weise das Ende der Ausgabe. Man sollte das Ausgabearray mit Nullen füllen, um das Ende der Liste zu finden.Ein vollständiges C ++ - Programm, das diesen Code verwendet:
Die Ausgabe weist einige Störungen auf, obwohl sie der Spezifikation folgt (keine Notwendigkeit zum Sortieren; keine Notwendigkeit zur Eindeutigkeit).
Eingabe: 69
Ausgabe:
Die Teiler sind paarweise.
Eingabe: 100
Ausgabe:
Für perfekte Quadrate wird der letzte Divisor zweimal ausgegeben (es ist ein Paar mit sich selbst).
Eingabe: 30
Ausgabe:
Wenn sich die Eingabe einem perfekten Quadrat nähert, wird das letzte Paar zweimal ausgegeben. Dies liegt an der Reihenfolge der Überprüfungen in der Schleife: Zuerst wird nach "Rest = 0" und Ausgaben gesucht, und erst dann wird nach "Quotient <Divisor" gesucht, um die Schleife zu verlassen.
quelle
SmileBASIC, 49 Bytes
Verwendet die Tatsache, dass
D>N/D
=D>sqrt(N)
für positive Zahlenquelle
C
8781 BytesVerbessert durch @ceilingcat , 81 Bytes:
Probieren Sie es online aus!
Meine ursprüngliche Antwort, 87 Bytes:
Kompilieren mit
gcc div.c -o div -lm
und ausführen mit./div <n>
.Bonus: Eine noch kürzere Variante mit O (n) Zeitkomplexität und fest codiert
n
(46 Bytes + Länge vonn
):Bearbeiten: Vielen Dank an @Sriotchilism O'Zaic für den Hinweis, dass Eingaben nicht fest codiert werden sollten. Ich habe die Hauptübermittlung geändert, um die Eingabe über argv zu übernehmen.
quelle
n
die Eingabe? Das Einfügen der Eingabe in eine Variable ist aus mehreren Gründen keine akzeptierte Methode zum Eingeben. Weitere Informationen zu unseren akzeptierten und nicht akzeptierten Eingabe- und Ausgabeformularen finden Sie hier: codegolf.meta.stackexchange.com/questions/2447/… . Und wenn Sie neugierig auf eine bestimmte Sprache sind (z. B. C), können Sie hier nachsehen : codegolf.meta.stackexchange.com/questions/11924/… .n
ist die Eingabe. Ich werde versuchen, es so zu ändern, dass die Eingabe auf eine andere Weise erfolgt. Danke für die Info!APL (NARS), 22 Zeichen, 44 Bytes
Prüfung:
quelle
C # (Visual C # Interactive Compiler) , 40 Byte
Nur eine aktualisierte C # -Antwort bereitstellen
Probieren Sie es online aus!
quelle