Nein, das meine ich nicht ϕ = 1.618...
und π = 3.14159...
. Ich meine die Funktionen .
- φ (x) ist die Anzahl von ganzen Zahlen, die kleiner oder gleich der Zahl
x
sind, zu der eine relative Primzahl bestehtx
. - π (x) ist die Anzahl der Primzahlen kleiner oder gleich
x
. - Nehmen wir an, dass "nicht pi" dann π̅ (x) ist, und definieren Sie es als die Anzahl der Komposite, die kleiner oder gleich sind
x
.
Aufgabe
Bei einer streng positive ganze Zahl ist x
, berechnen φ (& pi; (x)) . Die Bewertung erfolgt in Byte.
Beispiele
Jede Zeile besteht aus der Eingabe (von 1 bis einschließlich 100) und der entsprechenden Ausgabe, die durch ein Leerzeichen getrennt sind.
1 0
2 0
3 0
4 1
5 1
6 1
7 1
8 2
9 2
10 4
11 4
12 2
13 2
14 6
15 4
16 6
17 6
18 4
19 4
20 10
21 4
22 12
23 12
24 6
25 8
26 8
27 16
28 6
29 6
30 18
31 18
32 8
33 12
34 10
35 22
36 8
37 8
38 20
39 12
40 18
41 18
42 12
43 12
44 28
45 8
46 30
47 30
48 16
49 20
50 16
51 24
52 12
53 12
54 36
55 18
56 24
57 16
58 40
59 40
60 12
61 12
62 42
63 20
64 24
65 22
66 46
67 46
68 16
69 42
70 20
71 20
72 32
73 32
74 24
75 52
76 18
77 40
78 24
79 24
80 36
81 28
82 58
83 58
84 16
85 60
86 30
87 36
88 32
89 32
90 48
91 20
92 66
93 32
94 44
95 24
96 70
97 70
98 24
99 72
100 36
Verwenden Sie diesen Link , um die erwartete Ausgabe für eine Eingabe zu berechnen. Auch eine Liste der Ein- und Ausgänge für x <= 1000
vorgesehen ist hier auf Pastebin . (Mit diesem Minkolang-Programm erstellt .)
Bestenlisten
Hier ist ein Stack-Snippet, um sowohl eine reguläre Rangliste als auch eine Übersicht der Gewinner nach Sprache zu generieren.
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 N
ist 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 Leaderboard-Snippet angezeigt wird:
## [><>](http://esolangs.org/wiki/Fish), 121 bytes
quelle
Antworten:
GS2 ,
1210 BytesDer Quellcode verwendet die CP437- Codierung. Probieren Sie es online!
Testlauf
Wie es funktioniert
quelle
Regex (.NET),
122113 BytesAngenommen, Eingabe und Ausgabe sind unär, und die Ausgabe wird aus der Hauptübereinstimmung des regulären Ausdrucks entnommen.
Aufschlüsselung des regulären Ausdrucks:
^(?=((?=.*$(?<=^(\3+(.+.))(.*?(?>(.\4)?)))).)+(.*))
berechnet π̅ (x) und erfasst den Rest der Zeichenkette in Erfassungsgruppe 6 zur Bestätigung im zweiten Teil..*$
Setzt den Zeiger auf das Ende der Zeichenkette, so dass wir die ganze Zahlx
in eine Richtung haben.(?<=^(\3+(.+.))(.*?(?>(.\4)?)))
Stimmt von rechts nach links überein und sucht nach zusammengesetzten Zahlen, indem Sie von x nach 0 wechseln.(.*?(?>(.\4)?))
ist eine "Variable", die bei der ersten Iteration mit 0 beginnt und bei der vorherigen Iteration mit der Zahl fortfährt und bis zu x durchläuft. Da die kleinste zusammengesetzte Zahl 4 ist, wird(.\4)?
die Übereinstimmung nicht beeinträchtigt, wenn die Erfassungsgruppe 4 verfügbar ist.^(\3+(.+.))
prüft, was von der "Variablen" oben übrig bleibt (dhx - "variable"
ob es sich um eine zusammengesetzte Zahl handelt).((?=.*(?=\6$)(?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?)))).)+
berechnet φ (π̅ (x)) durch Begrenzen der Operationen von links nach rechts mit(?=\6$)
..*(?=\6$)
Setzt den Zeiger auf die Position π̅ (x). Wir bezeichnen y = π̅ (x).(?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?)))
Stimmt von rechts nach links überein und überprüft die relative Primzahl durch Schleifen von (y - 1) auf 0(.+?(?>\9?))
ist eine "Variable", die bei der ersten Iteration mit 1 beginnt und bei der vorherigen Iteration mit der Zahl fortfährt und bis zu y durchläuft(?!(.+.)\8*(?=\6$)(?<=^\8+))
Entspricht von links nach rechts 1 und prüft, ob die "Variable" und y relative Primzahlen sind.(.+.)\8*(?=\6$)
wählt einen Teiler von "Variable", der größer als 1 ist, und ein Nebeneffekt ist, dass wir links die ganze Zahl y haben.(?<=^\8+)
prüft, ob der Teiler von "Variable" auch der Teiler von y ist.1 In .NET legt Look-Ahead die Richtung auf LTR fest, anstatt der aktuellen Richtung zu folgen. Look-Behind stellt die Richtung auf RTL ein, anstatt die Richtung umzukehren.
Testen Sie den Regex bei RegexStorm .
Revision 2 löscht nicht erfassende Gruppen und verwendet atomare Gruppen anstelle der bedingten Syntax.
quelle
J,
1514 BytesDies ist ein stillschweigendes, monadisches Verb. Probieren Sie es online mit J.js .
Wie es funktioniert
quelle
Im Ernst , 27 Bytes
Ja, ich habe CJam geschlagen! Probieren Sie es online aus
Erklärung (
a
bezieht sich auf den oberen Teil des Stapels,b
bezieht sich auf den zweiten Teil von oben):Hinweis: Seit dem Versenden dieser Antwort habe ich die Funktionen pi und phi zu Seriously hinzugefügt. Hier ist eine nicht wettbewerbsfähige Antwort mit diesen Funktionen:
Erläuterung (einige Befehle werden verschoben, um andere nicht zu überlappen):
quelle
Julia,
5250 BytesDadurch wird eine unbenannte Funktion erstellt, die eine Ganzzahl akzeptiert und eine Ganzzahl zurückgibt. Um es zu nennen, geben Sie ihm einen Namen, z
f=x->...
.Ungolfed:
quelle
sum
anstelle voncount
, um einige Zeichen zu speichern. Es ist allerdings ein wenig frustrierend - die andere Art, die Primzahlen zu zählensum(isprime,1:x)
, ist genau so lang wieendof(primes(x))
.sum
schlägt aber für leere Sammlungen fehl undcount
gibt 0 zurück. Dahersum
wird für nicht das gewünschte Ergebnis erzieltx<4
.Mathematica, 24 Bytes
quelle
PhiNotPi@#&
: 11 Bytes: PPyth, 14 Bytes
Demonstration , Verifizierer
Wir berechnen Verbundwerkstoffe mit einem einfachen Filter, nehmen seine Länge und speichern es in
J
. Dann nehmen wir den gcd vonJ
mit jeder Zahl bis zuJ
und zählen, wie viele Ergebnisse gleich 1 sind.quelle
Minkolang 0.11 , 12 Bytes (NICHT konkurrenzfähig)
Diese Antwort ist NICHT wettbewerbsfähig. Ich habe pi und phi als Built-In implementiert, bevor ich die Frage gestellt habe, was mir einen unfairen Vorteil verschafft. Ich poste dies nur für diejenigen, die sich für die Sprache interessieren.
Probieren Sie es hier aus.
Erläuterung
quelle
CJam, 28 Bytes
Probieren Sie es mit dieser Funktion im CJam-Interpreter aus oder überprüfen Sie alle Testfälle auf einmal .
Wie es funktioniert
quelle
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
. Ist das richtig?Python, 137
139quelle
range(n) if
und entfernen])) if
Netzhaut , 48 Bytes
Probieren Sie es online!
Erläuterung
Eingabe in Unär umwandeln.
Zählen Sie zusammengesetzte Zahlen, die nicht größer als die Eingabe sind, indem Sie zählen, wie oft eine Zeichenfolge gefunden werden kann, die aus mindestens zwei Wiederholungen mit einem Faktor von mindestens 2 besteht.
Konvertiere wieder zu Unary.
Berechnen Sie φ, indem Sie zählen, an wie vielen Positionen es nicht möglich ist, einen Faktor (von mindestens 2) des Suffixes von der Position zu finden, die auch ein Faktor des Präfixes ist (wenn wir einen solchen Faktor finden, dann
i <= n
teilt dieser einen Faktor mitn
ist also kein coprime dazu). Das.
am Ende stellt sicher, dass wir keine Null zählen (für die wir keinen Faktor von mindestens 2 finden können).quelle
Regex (.NET),
8886 BytesProbieren Sie es online!(Als Retina-Programm.)
Verwendet das gleiche I / O wie die Antwort von n̴̖̋h̴̖̋ã̷͉h̷̭̿d̷̰̀ĥ̷̳ Eingabe , dh eine unäre Eingabe, und stimmt mit einer Teilzeichenfolge der Länge des Ergebnisses überein.
Möglicherweise kann dies weiter verkürzt werden, indem einer oder beide Bilanzkreise durch Vorwärtsreferenzen ersetzt werden.
Alternative bei gleicher Byteanzahl:
Es gibt auch einige Alternativen für die erste Hälfte, z. B. die Verwendung eines negativen Vorgriffs anstelle eines positiven Vorgriffs für die zusammengesetzten Zahlen oder die Verwendung einer Bedingung auch dort.
Erläuterung
Ich gehe davon aus, dass Sie ein grundlegendes Verständnis für Bilanzgruppen haben , aber kurz gesagt, Capturing-Gruppen in .NET sind Stapel (dh, jedes Mal, wenn Sie die Capturing-Gruppe wiederverwenden, wird das neue Capture nach oben
(?<-x>...)
verschoben ) und es wird ein Capture aus dem Stapel gezogenx
. Das ist sehr hilfreich, um Dinge zu zählen.quelle
PARI / GP, 27 Bytes
quelle
Gelee , nicht konkurrierend
7 Bytes Diese Antwort ist nicht konkurrierend, da sie eine Sprache verwendet, die die Herausforderung datiert.
Wie es funktioniert
quelle
Octave,
5251Edit: 1 Byte dank Thomas Kwa gespeichert
Erläuterung:
quelle
PARI / GP, 35 Bytes
quelle
SageMath 26 Bytes
Funktioniert auch für
n=0
undn=1
dank der Implementierung von Sage.quelle
Gelee , 6 Bytes
Probieren Sie es online!
Dies ist eine Zusammenarbeit zwischen Caird Coinheringahhing und Mr. Xcoder im Chat
Erläuterung
quelle
Gaia , 5 Bytes
Probieren Sie es online!
quelle
Ohm v2 , 7 Bytes
Probieren Sie es online!
quelle
MATL , 9 Bytes (nicht konkurrierend)
Diese Antwort ist nicht konkurrierend, da die Sprache die Herausforderung datiert.
Verwendet die Version (10.1.0) der Sprache / des Compilers.
Probieren Sie es online!
Erläuterung
quelle
GAP, 33 Bytes
Number(l,p)
zählt, wie viele Elemente vonl
erfüllenp
. Um zu kompensieren, dass 1 weder eine Primzahl noch eine zusammengesetzte Zahl ist, muss ich von n eins mehr als die Anzahl der Primzahlen bis zu n subtrahieren. Anstatt-1
für zwei Bytes zu tun , beginne ich die Liste mit -2 anstelle von 1 oder 2 und füge so eine weitere Zahl hinzu, dieIsPrime
für nur ein zusätzliches Byte als Primzahl betrachtet wird .quelle
Python 3.5 - 130 Bytes
Wenn es nicht akzeptabel ist, die Funktion als p (n, 0,0) durchzuleiten, dann +3 Bytes.
Dies nutzt die Tatsache aus, dass ich den Satz von Wilson verwende, um zu überprüfen, ob eine Zahl zusammengesetzt ist, und das Mathematikmodul für die Fakultätsfunktion aufrufen muss. Python 3.5 fügte dem Mathematikmodul eine gcd-Funktion hinzu.
Die erste Schleife des Codes erhöht k um eins, wenn die Zahl zusammengesetzt ist, und erhöht sich ansonsten um 0. (Obwohl der Satz von Wilson nur für ganze Zahlen größer als 1 gilt, wird 1 als Primzahl behandelt, sodass wir dies ausnutzen können.)
Die zweite Schleife durchläuft dann den Bereich der Anzahl der Komposite und erhöht g nur dann, wenn der Wert von nicht pi und l Co-Prim sind.
g ist dann die Anzahl der Werte kleiner oder gleich der Anzahl der zusammengesetzten Zahlen kleiner oder gleich n.
quelle
Python 3 + Sympy ,
5958 Bytes* -1 Byte durch Ersetzen
compositepi(k)
durchk+~primepi(k)
.Probieren Sie es online!
quelle
05AB1E ,
118 BytesProbieren Sie es online!
Dies könnte nicht konkurrierend sein - ich kann nicht herausfinden, wann 05AB1E hergestellt wurde.
Wie es funktioniert
quelle
Pyt , 6 Bytes
Erläuterung:
Probieren Sie es online!
quelle
APL NARS, 38 Byte, 19 Zeichen
13π ist die Summenfunktion und 2π ist die Zählprimusfunktion <= ihr Argument. Prüfung
quelle
Add ++ , 21 Bytes
Probieren Sie es online!
Wie es funktioniert
Dies wird einfach implementiertπ¯¯¯( n ) und φ ( n ) ohne die zwei expliziten Funktionen zu verwenden (hauptsächlich, weil sie nicht eingebaut sind). Der Code kann daher in zwei Abschnitte unterteilt werden:π¯¯¯( n ) und φ ( n ) .
Hier erzeugen wir bei direkter Eingabe einen Bereich von [0 .. n] mitx = π¯¯¯(n ) auf dem Stapel.
R
und entfernen dann alle Primzahlen mitþP
(filter false (þ
) prime elements (P
)). Leider entfernt dies nicht 1 , da es nicht prim ist. Nachdem wir die Anzahl derbL
verbleibenden Elemente genommen haben , dekrementieren wir einmal1_
, um die Anzahl für 1 zu entfernen . Diese BlätterDieser ist etwas länger, was wiederum auf 1 zurückzuführen ist . Zuerst duplizieren wirX und erstellen Sie einen Bereich, mit dem Sie arbeiten können X , oder behalten Sie alle Elemente bei, die eine GCD von 1 mit habenX . Zum Schluss nehmen wir die Länge dieser Liste mit
dR
. Als Nächstes speichern wir eine Kopie dieses Bereichs für eine Überprüfung, auf die wir später eingehen werden. DannÞ%
entfernen wir mit filter true alle Elemente, die sich teilenbL
.Leider ergibt dies 0, wenn das Ergebnis 0 und sein sollten - 1 wenn das richtige Ergebnis ist n . Um diese Diskrepanz zu beheben, rufen wir den gespeicherten Bereich mit ab
G
und konvertieren ihn mit in einen Booleschen Wert!!
. Dies macht leere Bereiche (die 0 ergeben würden ) zu 0 und jeden anderen Bereich zu 1 . Schließlich addieren wir diesen Wert zu unserem vorherigen Ergebnis und geben ihn zurück.Ja, ich wollte das neue LaTex unbedingt ausprobieren
quelle