Berechne Phi (nicht Pi)

73

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 xsind, 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 sindx .

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 <= 1000vorgesehen 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 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 Leaderboard-Snippet angezeigt wird:

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

El'endia Starman
quelle
Gibt es Grenzen für die Größe der Eingabe?
Lirtosiast
4
Ist diese Frage eine Hommage an den Benutzer PhiNotPi ?
Primo
24
@primo Warum denkst du das?
Mego
2
@primo: Es war von seinem Namen inspiriert und definitiv ein Wortspiel, aber nicht gerade eine Hommage an ihn.
El'endia Starman
1
@ edc65: Ja anscheinend so , wie ich gestern herausgefunden habe.
El'endia Starman

Antworten:

27

GS2 , 12 10 Bytes

V@'◄l.1&‼l

Der Quellcode verwendet die CP437- Codierung. Probieren Sie es online!

Testlauf

$ xxd -r -ps <<< 564027116c2e3126136c > phinotpi.gs2
$ wc -c phinotpi.gs2 
10 phinotpi.gs2
$ gs2 phinotpi.gs2 <<< 1000
552

Wie es funktioniert

V          Read an integer n from STDIN.
 @         Push a copy of n.
  '        Increment the copy of n.
   ◄l      Push 1 and call primes; push the list of all primes below n+1.
     .     Count the primes.
      1    Subtract the count from n.
       &   Decrement to account for 1 (neither prime nor composite).
        ‼l Push 3 and call primes; apply Euler's totient function.
Dennis
quelle
25
Der Dateiname ist länger als das Programm.
Floris
43

Regex (.NET), 122 113 Bytes

^(?=((?=.*$(?<=^(\3+(.+.))(.*?(?>(.\4)?)))).)+(.*))((?=.*(?=\6$)(?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?)))).)+

Angenommen, 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 Zahl xin 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 (dh x - "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.

n̴̖̋h̴̖̋ã̷͉h̷̭̿d̷̰̀ĥ̷̳
quelle
24
Sir, Sie sind verrückt.
RK.
9
Er hat einen Hauch von Zalgo, glaube ich.
curiousdannii
11
Und jetzt hast du zwei Probleme. (Hatte ernsthaft keine Ahnung, dass Sie so etwas mit Regex machen könnten ...)
Darrel Hoffman
21

J, 15 14 Bytes

5 p:<:-_1 p:>:

Dies ist ein stillschweigendes, monadisches Verb. Probieren Sie es online mit J.js .

Wie es funktioniert

                Right argument: y
            >:  Increment y.
       _1 p:    Calculate the number of primes less than y+1.
    <:          Decrement y.
      -         Calculate the difference of the results to the left and right.
5 p:            Apply Euler's totient function to the difference.
Dennis
quelle
14
Ich kann das erklären. : P
anOKsquirrel 13.11.15
23
Ich has hinzugefügt Erklärung
Dennis
5
Ich wollte gerade sagen, dass ich dies hochgestuft habe, weil es viele Smileys hat, aber der Text sagte mir, diese zu vermeiden :(
Doddy
@Dennis: Deine erste Antwort hat mich ziemlich zum Lachen gebracht, danke dafür!
Mehrdad
19

Im Ernst , 27 Bytes

,;R`p`MΣ(-D;n;;╟@RZ`ig1=`MΣ

Ja, ich habe CJam geschlagen! Probieren Sie es online aus

Erklärung ( abezieht sich auf den oberen Teil des Stapels, bbezieht sich auf den zweiten Teil von oben):

,;       take input and duplicate it
R`p`MΣ   push sum([is_prime(i) for i in [1,...,a]]) (otherwise known as the pi function)
(-D      rotate stack right by 1, subtract top two elements, subtract 1, push
            (@ could be used instead of (, but I was hoping the unmatched paren would bother someone)
;n;;     dupe top, push a b times, dupe top twice (effectively getting a a+1 times)
╟        pop n, pop n elements and append to list, push
@        swap top two elements
RZ       push [1,...,a], zip a and b
`ig1=`   define a function:
  i        flatten list
  g1=      compute gcd(a,b), compare to 1 (totient function)
MΣ       perform the function a on each element of b, sum and push

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:

,;▓1-@-▒

Erläuterung (einige Befehle werden verschoben, um andere nicht zu überlappen):

,    get input (hereafter referred to as x)
;    duplicate x
 ▓   calculate pi(x) (we'll call this p)
1-   calculate 1-p
@-   bring x back on top, calculate x-1-p (not pi(x))
  ▒  calculate phi(not pi(x))
Mego
quelle
1
Sie haben ernsthaft @Dennis OUTGOLFED!
TanMath
Bitte sag mir nicht, dass du das oben auf deinem Kopf
wusstest
1
GJ schlägt CJam =)
flawr
14

Julia, 52 50 Bytes

x->count(i->gcd(i,p)<2,1:(p=x-endof(primes(x))-1))

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

function phinotpi(x::Integer)
    # The number of composites less than or equal to x is
    # x - the number of primes less than or equal to x -
    # 1, since 1 is not composite
    p = x - length(primes(x)) - 1

    # Return the number of integers i between 1 and p such
    # that gcd(i, p) = 1. This occurs when i is relatively
    # prime to p.
    count(i -> gcd(i, p) == 1, 1:p)
end
Alex A.
quelle
Verwenden Sie sumanstelle von count, um einige Zeichen zu speichern. Es ist allerdings ein wenig frustrierend - die andere Art, die Primzahlen zu zählen sum(isprime,1:x), ist genau so lang wie endof(primes(x)).
Glen O
1
@GlenO Vielen Dank für den Vorschlag, sumschlägt aber für leere Sammlungen fehl und countgibt 0 zurück. Daher sumwird für nicht das gewünschte Ergebnis erzielt x<4.
Alex A.
8

Mathematica, 24 Bytes

EulerPhi[#-PrimePi@#-1]&
LegionMammal978
quelle
2
Natürlich hat Mathematica all dies eingebaut ...
klatschen
@ConfusedMr_C Offensichtlich :) Es wurde jedoch aus einem offensichtlichen Grund nicht disqualifiziert: Mathematische Software kann Golfsprachen in einfachen kombinatorischen Aufgaben nicht schlagen :)
yo
@ConfusedMr_C PhiNotPi@#&: 11 Bytes: P
LegionMammal978
8

Pyth, 14 Bytes

JlftPTSQ/iLJJ1

Demonstration , Verifizierer

Wir berechnen Verbundwerkstoffe mit einem einfachen Filter, nehmen seine Länge und speichern es in J. Dann nehmen wir den gcd von Jmit jeder Zahl bis zu Jund zählen, wie viele Ergebnisse gleich 1 sind.

isaacg
quelle
7

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.

nd9M-1-9$MN.

Probieren Sie es hier aus.

Erläuterung

n      Read in integer from input
d      Duplicate
9M     Pops off the top of stack as x and pushes pi(x)
-      Subtracts the top two elements on the stack (x - pi(x))
1-     Subtracts 1 (x-1 - pi(x))
9$M    Pops off the top of stack as x and pushes phi(x) (phi(x-1 - pi(x)))
N.     Outputs as integer and stops.
El'endia Starman
quelle
2
Ich halte es nicht für eine gute Idee, ungültige Antworten zu veröffentlichen ...
yeti
20
Solange sie einen Haftungsausschluss haben, glaube ich nicht, dass daran etwas falsch ist. Es ist eigentlich ziemlich häufig für ältere Herausforderungen.
Dennis
4
@yeti: Technisch ist es nicht ungültig. Die hier verwendeten Funktionen wurden alle implementiert, bevor die Herausforderung veröffentlicht wurde. Ich disqualifiziere es einfach, weil ich die Veröffentlichung der Herausforderung verzögert habe, bis zwei bestimmte Funktionen implementiert wurden (die ich übrigens zur Erstellung der Beispiellisten verwendet habe).
El'endia Starman
1
Gleich. Ich mache das oft, wenn 𝔼𝕊𝕄𝕚𝕟 immer auf dem Laufenden bleibt.
Mama Fun Roll
6

CJam, 28 Bytes

ri){mf1>},,_,f{){_@\%}h)=}1b

Probieren Sie es mit dieser Funktion im CJam-Interpreter aus oder überprüfen Sie alle Testfälle auf einmal .

Wie es funktioniert

ri                            Read an integer N from STDIN.
  )                           Increment it. 
   {    },                    Filter; for each I in [0 ... N]:
    mf                          Push I's prime factorization.
      1>                        Discard the first prime.
                              If there are primes left, keep I.
          ,                   Count the kept integers. Result: C
           _,                 Push [0 ... C-1].
             f{          }    For each J in [0 ... C-1], push C and J; then:
               )                Increment J.
                {    }h         Do:
                 _                Push a copy of the topmost integer..
                  @               Rotate the integer below on top of it.
                   \%             Take that integer modulo the other integer.
                                If the residue is non-zero, repeat the loop.
                                This computes the GCD of C and J+1 using the
                                Euclidean algorithm.
                       )        Increment the 0 on the stack. This pushes 1.

                        =     Push 1 if the GCD is 1, 0 if not.
                          1b  Add all Booleans.
Dennis
quelle
Ich versuchte , die „alle Fälle überprüfen“ -Link und bekam dies: 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111. Ist das richtig?
El'endia Starman
Ja, es wird überprüft, ob das Anwenden des Codes auf die linke Spalte (Eingabe) der rechten Spalte (Ausgabe) entspricht.
Dennis
5
Ich kann erklären, auf dis1 haz?
anOKsquirrel
9
@anOKsquirrel ich haz erklärt dis1 2
Dennis
5
@Dennis kthxbai
anOKsquirrel
5

Python, 137 139

n=input()
print n,len([b for b in range(len([a for a in range(n)if not all(a%i for i in xrange(2,a))]))if all(b%i for i in xrange(2,b))])
wnnmaw
quelle
2
Ich denke, Sie können 2 Bytes sparen, indem Sie die Leerzeichen zwischen range(n) ifund entfernen])) if
DankMemes
3
Angesichts der relativ geringen Golffähigkeit von Python (aufgrund der Leerraumanforderungen usw.) ist dies ziemlich beeindruckend!
Felixphew
@DankMemes, danke für den Tipp!
Wnnmaw
5

Netzhaut , 48 Bytes

.+
$*
M&`(..+)\1+$
.+
$*
(?!(..+)\1*$(?<=^\1+)).

Probieren Sie es online!

Erläuterung

.+
$*

Eingabe in Unär umwandeln.

M&`(..+)\1+$

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.

(?!(..+)\1*$(?<=^\1+)).

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 <= nteilt dieser einen Faktor mit nist 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).

Martin Ender
quelle
5

Regex (.NET), 88 86 Bytes

^(?=((?=(..+)\2+$)?.)+)(?=(?<-2>.)*(.+))(?=(((?!(..+)\6*(?<=^\6+)\3$))?.)*\3)(?<-5>.)*

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

^(?=((?=(..+)\2+$)?.)+)(?=(?<-2>.)*(.+))(?=(?((..+)\4*(?<=^\4+)\3$).|(.))*\3)(?<-5>.)*

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 gezogen x. Das ist sehr hilfreich, um Dinge zu zählen.

^                   # Only look at matches from the beginning of the input.
(?=                 # First, we'll compute the number of composites less than
                    # or equal to the input in group 2. This is done in a
                    # lookahead so that we don't actually advance the regex
                    # engine's position in the string.
  (                 #   Iterate through the input, one character at a time.
    (?=(..+)\2+$)?  #     Try to match the remainder of the input as a
                    #     composite number. If so the (..+) will add one
                    #     one capture onto stack 2. Otherwise, this lookahead
                    #     is simply skipped.
    .
  )+
)
(?=                 # It turns out to be more convienient to work with n minus
                    # the number of composites less than or equal to n, and to
                    # have that a single backreference instead of the depth of
                    # a stack.
  (?<-2>.)*         #   Match one character for each composite we found.
  (.+)              #   Capture the remainder of the input in group 3.
)
(?=                 # Now we compute the totient function. The basic idea is
                    # similar to how we computed the number of composites,
                    # but there are a few differences.
                    # a) Of course the regex is different. However, this one
                    #    is more easily expressed as a negative lookahead (i.e.
                    #    check that the values don't share a factor), so this
                    #    won't leave a capture on the corresponding stack. We
                    #    fix this by wrapping the lookahead itself in a group
                    #    and making the entire group optional.
                    # b) We only want to search up the number of composites,
                    #    not up to the input. We do this by asserting that we
                    #    can still match our backreference \3 from earlier.

  (                 #   Iterate through the input, one character at a time.
    ((?!            #     Try not to match a number that shares a factor with
                    #     the number of composites, and if so push a capture
                    #     onto stack 5.
      (..+)\6*      #     Look for a factor that's at least 2...
      (?<=^\6+)     #     Make sure we can reach back to the input with that
                    #     factor...
      \3$           #     ...and that we're exactly at the end of the number
                    #     of composites.
    ))?
    .
  )*
  \3                #   Match group 3 again to make sure that we didn't look
                    #   further than the number of composites.
)
(?<-5>.)*           # Finally, match one character for each coprime number we
                    # found in the last lookahead.
Martin Ender
quelle
4

PARI / GP, 27 Bytes

n->eulerphi(n-1-primepi(n))
Charles
quelle
4

Gelee , nicht konkurrierend

7 Bytes Diese Antwort ist nicht konkurrierend, da sie eine Sprache verwendet, die die Herausforderung datiert.

ÆC_@’ÆṪ

Wie es funktioniert

ÆC_@’ÆṪ  Input: n

ÆC       Count the primes less than or equal to n.
    ’    Yield n - 1.
  _@     Subtract the count from n - 1.
     ÆṪ  Apply Euler's totient function.
Dennis
quelle
3

Octave, 52 51

@(b)nnz((d=[1:(c=b-1-nnz(primes(b)))])(gcd(d,c)<2))

Edit: 1 Byte dank Thomas Kwa gespeichert

Erläuterung:

@(b)                                            # Define anonymous func with parameter b
  nnz(                                          # Count elements in φ(c)
    (                                           #
      d = [1:                                   # Create d= array of 1 to π̅(b)
            ( c = b - 1 - nnz(primes(b)) )      # Calculate c=π̅(b) by subtracting the
                                                #  number of elements in the array of prime
          ]                                     #  numbers from the number of ints in 2:b
    )(gcd(d, c) < 2)                            # Calculate φ(c) by using gcd to filter
  )                                             # relative primes from d
DankMemes
quelle
3

PARI / GP, 35 Bytes

n->eulerphi(sum(x=2,n,!isprime(x)))
Alephalpha
quelle
3

SageMath 26 Bytes

euler_phi(n-1-prime_pi(n))

Funktioniert auch für n=0und n=1dank der Implementierung von Sage.

yo '
quelle
3

Gelee , 6 Bytes

_ÆC’ÆṪ

Probieren Sie es online!

Dies ist eine Zusammenarbeit zwischen Caird Coinheringahhing und Mr. Xcoder im Chat

Erläuterung

_ÆC'ÆṪ ~ Volles Programm.

 ÆC ~ Zähle die Primzahlen kleiner oder gleich Z.
_ ~ Von der Eingabe subtrahieren.
   '~ Dekrement.
    ÆṪ ~ Eulers Totientenfunktion.
caird coinheringaahing
quelle
3

Gaia , 5 Bytes

ṗ⁈l(t

Probieren Sie es online!

Vollständiges Programm.

 ⁈ ~ Lehne die Elemente ab, die:
ṗ ~ Sind prime.
  l ~ Länge.
   (~ Dekrement.
    Euler ist totient.
Mr. Xcoder
quelle
2

MATL , 9 Bytes (nicht konkurrierend)

Diese Antwort ist nicht konkurrierend, da die Sprache die Herausforderung datiert.

:Zp~sq_Zp

Verwendet die Version (10.1.0) der Sprache / des Compilers.

Probieren Sie es online!

Erläuterung

:       % implicitly input a number "N" and produce array [1,2,...,N]
Zp      % true for entries that are prime
~       % negate. So it gives true for entries of [1,2,...,N] that are non-prime
s       % sum elements of array. So it gives number of non-primes
q       % subtract 1. Needed because number 1 is not prime, but not composite either
_       % unary minus
Zp      % with negative input, computes totient function of absolute value of input
        % implicit display
Luis Mendo
quelle
2

GAP, 33 Bytes

n->Phi(n-Number([-2..n],IsPrime))

Number(l,p)zählt, wie viele Elemente von lerfüllen p. 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 -1für zwei Bytes zu tun , beginne ich die Liste mit -2 anstelle von 1 oder 2 und füge so eine weitere Zahl hinzu, die IsPrimefür nur ein zusätzliches Byte als Primzahl betrachtet wird .

Christian Sievers
quelle
2

Python 3.5 - 130 Bytes

from math import*
def p(n,k,g):
 for i in range(1,n+1):k+=factorial(i-1)%i!=i-1
 for l in range(1,k):g+=gcd(k,l)<2      
 return g

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.

Joe Habel
quelle
1

05AB1E , 11 8 Bytes

LDpÈÏg<Õ

Probieren Sie es online!

Dies könnte nicht konkurrierend sein - ich kann nicht herausfinden, wann 05AB1E hergestellt wurde.

Wie es funktioniert

L             # this gets us the list of numbers [1 .. a]
 D            # duplicates this list
  p           # applies isPrime to each element of the list, vectorised.
   È          # is the element even? (does 05AB1E not have a logical not?)
    Ï         # push elements of the first list where the same index in the 
              # second list is 1
     g<       # finds the length and subtracts 1 (as the list contains 1)
              # this is the not pi function
       Õ      # euler totient function
Weltraumschrott
quelle
1

Pyt , 6 Bytes

řṗ¬Ʃ⁻Ț

Erläuterung:

                Implicit input
ř               Push [1,2,...,input]
 ṗ              [is 1 prime?, is 2 prime?, ..., is input prime?]
  ¬             [is 1 not prime?, is 2 not prime?, ... is input not prime?]
   Ʃ            Number of non-primes (sums the array - booleans implicitly converted to ints)
    ⁻           Subtract one to remove the counting of '1'
     Ț          Euler's totient function


Probieren Sie es online!

mudkip201
quelle
1

APL NARS, 38 Byte, 19 Zeichen

{⍵≤3:0⋄13π¯1+⍵-2π⍵}

13π ist die Summenfunktion und 2π ist die Zählprimusfunktion <= ihr Argument. Prüfung

  b←{⍵≤3:0⋄13π¯1+⍵-2π⍵}     
  (⍳12),¨b¨⍳12
1 0  2 0  3 0  4 1  5 1  6 1  7 1  8 2  9 2  10 4  11 4  12 2 
  (95..100),¨b¨(95..100)
95 24  96 70  97 70  98 24  99 72  100 36
RosLuP
quelle
1

Add ++ , 21 Bytes

L,RþPbL1_dRdVÞ%bLG!!+

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

π¯(n)

RþPbL1_

Hier erzeugen wir bei direkter Eingabe einen Bereich von [0 .. n] mit Rund 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 der bLverbleibenden Elemente genommen haben , dekrementieren wir einmal 1_, um die Anzahl für 1 zu entfernen . Diese BlätterX=π¯(n) auf dem Stapel.

φ(n)

dRdVÞ%bLG!!+

Dieser ist etwas länger, was wiederum auf 1 zurückzuführen ist . Zuerst duplizieren wirXund erstellen Sie einen Bereich, mit dem Sie arbeiten können 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 teilenX, oder behalten Sie alle Elemente bei, die eine GCD von 1 mit habenX. Zum Schluss nehmen wir die Länge dieser Liste mit bL.

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