Oblicz Phi (nie Pi)

73

Nie, nie mam na myśli ϕ = 1.618...i π = 3.14159.... Mam na myśli funkcje .

  • φ (x) jest liczbą całkowitą mniejszą lub równą, xktóra jest względnie podstawowa x.
  • π (x) to liczba liczb pierwszych mniejsza lub równa x.
  • Powiedzmy, że „not pi” to wtedy π̅ (x) i zdefiniujmy, że jest to liczba kompozytów mniejsza lub równa x.

Zadanie

Biorąc pod uwagę ściśle dodatnią liczbę całkowitą x, oblicz φ (π̅ (x)) . Punktacja jest w bajtach.

Przykłady

Każdy wiersz składa się z danych wejściowych (od 1 do 100 włącznie) i odpowiednich danych wyjściowych oddzielonych spacją.

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

Użyj tego łącza, aby obliczyć oczekiwany wynik dla dowolnego wejścia. Również lista wejść i wyjść dla x <= 1000znajduje się tutaj na pastebin . (Wygenerowano za pomocą tego programu Minkolang .)


Liderów

Oto fragment kodu, który pozwala wygenerować zarówno zwykłą tabelę wyników, jak i przegląd zwycięzców według języka.

Aby upewnić się, że Twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:

## Language Name, N bytes

gdzie Njest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:

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

Jeśli chcesz umieścić w nagłówku wiele liczb (np. Ponieważ twój wynik jest sumą dwóch plików lub chcesz osobno wymienić kary za flagi tłumacza), upewnij się, że rzeczywisty wynik jest ostatnią liczbą w nagłówku:

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

Możesz także ustawić nazwę języka jako link, który pojawi się we fragmencie tabeli wyników:

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

El'endia Starman
źródło
Czy istnieją ograniczenia dotyczące wielkości danych wejściowych?
lirtosiast
4
Czy to pytanie jest hołdem dla użytkownika PhiNotPi ?
primo
24
@primo Dlaczego tak myślisz?
Mego
2
@primo: Zostało zainspirowane jego nazwiskiem i zdecydowanie kalamburem, ale nie jest to dla niego hołd.
El'endia Starman
1
@ edc65: Tak, najwyraźniej tak , jak się wczoraj dowiedziałem.
El'endia Starman

Odpowiedzi:

27

GS2 , 12 10 bajtów

V@'◄l.1&‼l

Kod źródłowy używa kodowania CP437 . Wypróbuj online!

Testowe uruchomienie

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

Jak to działa

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
źródło
25
Nazwa pliku jest dłuższa niż program.
Floris,
43

Regex (.NET), 122 113 bajtów

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

Zakładając, że dane wejściowe i wyjściowe są jednoargumentowe, a dane wyjściowe są pobierane z głównego dopasowania wyrażenia regularnego.

Podział wyrażenia regularnego:

  • ^(?=((?=.*$(?<=^(\3+(.+.))(.*?(?>(.\4)?)))).)+(.*)) oblicza π̅ (x) i przechwytuje resztę ciągu w grupie przechwytywania 6 w celu potwierdzenia w drugiej części.

    • .*$ustawia wskaźnik na końcu ciągu, dzięki czemu mamy liczbę całkowitą xw jednym kierunku.
    • (?<=^(\3+(.+.))(.*?(?>(.\4)?))) dopasowuje od prawej do lewej i sprawdza liczbę złożoną, zapętlając od x do 0.
      • (.*?(?>(.\4)?))jest „zmienną”, która zaczyna się od 0 w pierwszej iteracji i kontynuuje od liczby w poprzedniej iteracji i zapętla do x. Ponieważ najmniejsza liczba złożona to 4, (.\4)?nigdy nie jest niezgodna, jeśli dostępna jest grupa przechwytywania 4.
      • ^(\3+(.+.))sprawdza, co pozostało z „zmiennej” powyżej (tj. x - "variable"), czy jest to liczba złożona.
  • ((?=.*(?=\6$)(?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?)))).)+oblicza φ (π̅ (x)), ograniczając operacje od lewej do prawej za pomocą (?=\6$).

    • .*(?=\6$)ustawia wskaźnik w pozycji π̅ (x). Oznaczmy y = π̅ (x).
    • (?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?))) dopasowuje od prawej do lewej i sprawdza względną liczbę pierwszą, zapętlając od (y - 1) do 0
      • (.+?(?>\9?)) jest „zmienną”, która zaczyna się od 1 w pierwszej iteracji i kontynuuje od liczby w poprzedniej iteracji i zapętla do y
      • (?!(.+.)\8*(?=\6$)(?<=^\8+))dopasowuje od lewej do prawej 1 i sprawdza, czy „zmienna” iy są liczbą pierwszą względną.
        • (.+.)\8*(?=\6$) wybiera dzielnik „zmiennej”, który jest większy niż 1, a efektem ubocznym jest to, że po lewej stronie mamy liczbę całkowitą y.
        • (?<=^\8+) sprawdza, czy dzielnik „zmiennej” jest również dzielnikiem y.

1 W .NET spojrzenie w przyszłość ustawia kierunek na LTR zamiast podążania za bieżącym kierunkiem; look-behind ustawia kierunek na RTL zamiast odwracania kierunku.

Przetestuj wyrażenie regularne w RegexStorm .

Wersja 2 usuwa grupy nie przechwytujące i używa grup atomowych zamiast składni warunkowej.

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳
źródło
24
Sir, jesteś szalony.
RK.
9
Myślę, że ma odrobinę Zalgo.
curiousdannii
11
A teraz masz dwa problemy. (Poważnie nie miałem pojęcia, że ​​możesz zrobić coś takiego z Regex ...)
Darrel Hoffman
21

J, 15 14 bajtów

5 p:<:-_1 p:>:

To jest milczący, monadyczny czasownik. Spróbuj go online z J.js .

Jak to działa

                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
źródło
14
mogę wyjaśnić Haz? : P
anOKsquirrel
23
I Haz dodał wyjaśnienie
Dennis
5
Już miałam powiedzieć, że głosowałem za tym, ponieważ ma wiele emotikonów, ale tekst kazał mi ich unikać :(
Doddy
@Dennis: Twoja pierwsza odpowiedź rozśmieszyła mnie bardzo, dzięki za to!
Mehrdad
19

Poważnie , 27 bajtów

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

Tak, pokonałem CJam! Wypróbuj online

Objaśnienie ( aodnosi się do początku stosu, bodnosi się do drugiego z góry):

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

Uwaga: od opublikowania tej odpowiedzi dodałem funkcje pi i phi do serio. Oto niekonkurencyjna odpowiedź z tymi funkcjami:

,;▓1-@-▒

Objaśnienie (niektóre polecenia są przesunięte, aby nie nakładały się na inne):

,    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
źródło
1
Masz POWAŻNIE WYGRANE @Dennis!
TanMath,
Nie mów mi, że wiedziałeś o tym na czubku głowy.
DividedByZero,
1
GJ pokonuje CJam =)
błąd
14

Julia, 52 50 bajtów

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

Spowoduje to utworzenie nienazwanej funkcji, która przyjmuje wartość całkowitą i zwraca liczbę całkowitą. Aby to nazwać, nadaj mu nazwę, np f=x->....

Nie golfowany:

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.
źródło
Użyj sumzamiast, countaby zapisać kilka znaków. Jest to jednak trochę frustrujące - inny sposób liczenia liczb pierwszych sum(isprime,1:x)jest taki sam jak endof(primes(x)).
Glen O
1
@GlenO Dziękuję za sugestię, ale sumkończy się niepowodzeniem za puste kolekcje, a countzwraca 0. W ten sposób sumnie da pożądanego wyniku x<4.
Alex A.,
8

Mathematica, 24 bajty

EulerPhi[#-PrimePi@#-1]&
LegionMammal978
źródło
2
Od kursu Mathematica ma wszystko wbudowane w ...
klaszczą
@ ConfusedMr_C Oczywiście :) Jednak nie zostało zdyskwalifikowane z oczywistego powodu: oprogramowanie matematyczne nie jest w stanie pokonać langug golfowych w prostych zadaniach kombinatorycznych :)
yo
@ConfusedMr_C PhiNotPi@#&: 11 bajtów: P
LegionMammal978,
8

Pyth, 14 bajtów

JlftPTSQ/iLJJ1

Demonstracja , weryfikator

Kompozyty obliczamy za pomocą prostego filtra, bierzemy jego długość i zapisujemy w J. Następnie bierzemy gcd Jz każdą liczbą do Ji liczymy, ile wyników jest równych 1.

isaacg
źródło
7

Minkolang 0.11 , 12 bajtów (NIE jest konkurencyjny)

Ta odpowiedź NIE jest konkurencyjna. Zaimplementowałem pi i phi jako wbudowane przed opublikowaniem pytania, co daje mi niesprawiedliwą przewagę. Publikuję to tylko dla tych, którzy są zainteresowani językiem.

nd9M-1-9$MN.

Wypróbuj tutaj.

Wyjaśnienie

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
źródło
2
Wydaje mi się, że publikowanie nieprawidłowych odpowiedzi nie jest dobrym pomysłem ...
yeti
20
Tak długo, jak mają zastrzeżenie, nie sądzę, aby było w tym coś złego. W rzeczywistości jest to dość powszechne w przypadku starszych wyzwań.
Dennis
4
@yeti: Technicznie to nie jest nieprawidłowe. Wszystkie użyte tutaj funkcje zostały wdrożone przed opublikowaniem wyzwania. Po prostu zdyskwalifikowałem go, ponieważ opóźniłem opublikowanie wyzwania, dopóki nie zostały zaimplementowane dwie szczególne funkcje (których przy okazji użyłem do wygenerowania list przykładów).
El'endia Starman
1
Podobnie. Często to robię, gdy 𝔼𝕊𝕄𝕚𝕟 ciągle się aktualizuje.
Mama Fun Roll
6

CJam, 28 bajtów

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

Wypróbuj to skrzypce w interpretatorze CJam lub sprawdź wszystkie przypadki testowe naraz .

Jak to działa

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
źródło
Próbowałem „Weryfikacja wszystkie przypadki” link i dostał to: 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111. Czy to prawda?
El'endia Starman
Tak, sprawdza, czy zastosowanie kodu do lewej kolumny (dane wejściowe) jest równe prawej kolumnie (dane wyjściowe).
Dennis
5
mogę wyjaśnić Haz na dis1?
anOKsquirrel
9
@anOKsquirrel i haz wyjaśnił 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
źródło
2
Myślę, że możesz zaoszczędzić 2 bajty, usuwając spacje między range(n) ifi])) if
DankMemes,
3
Biorąc pod uwagę stosunkowo niską zdolność golfową Pythona (ze względu na wymagania dotyczące białych znaków itp.), Jest to dość imponujące!
felixphew
@DankMemes, dzięki za wskazówkę!
wnnmaw
5

Siatkówka , 48 bajtów

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

Wypróbuj online!

Wyjaśnienie

.+
$*

Konwertuj dane wejściowe na jednoargumentowe.

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

Policz liczby złożone nie większe niż dane wejściowe, licząc, jak często możemy dopasować ciąg znaków, który składa się z co najmniej dwóch powtórzeń współczynnika co najmniej 2.

.+
$*

Konwertuj ponownie na unary.

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

Oblicz φ, licząc od tego, ile pozycji nie jest w stanie znaleźć współczynnika (co najmniej 2) sufiksu z tej pozycji, który jest również współczynnikiem prefiksu (jeśli znajdziemy taki czynnik, to i <= ndzieli to czynnik z nnie jest zatem chroniony prawem autorskim). Na .końcu gwarantuje, że nie liczymy zera (dla którego nie możemy znaleźć współczynnika co najmniej 2).

Martin Ender
źródło
5

Regex (.NET), 88 86 bajtów

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

Wypróbuj online! (Jako program Retina.)

Używa tego samego wejścia / wyjścia co odpowiedź n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳ , tj. Jednoargumentowego wejścia i dopasowuje podciąg długości wyniku.

Możliwe może być dalsze skrócenie tego procesu poprzez zastąpienie jednej lub obu grup bilansujących referencjami do przodu.

Alternatywa przy tej samej liczbie bajtów:

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

Istnieją również alternatywy dla pierwszej połowy, np. Użycie negatywnego spojrzenia w przód zamiast pozytywnego dla liczb kompozytowych lub użycie warunkowego również tam.

Wyjaśnienie

Zakładam, że masz podstawową wiedzę na temat równoważenia grup , ale w skrócie, grupy przechwytywania w .NET są stosami (więc za każdym razem, gdy użyjesz grupy przechwytywania, nowe przechwytywanie jest umieszczane na górze) i (?<-x>...)wyskakuje przechwytywanie ze stosu x. To bardzo pomocne w liczeniu rzeczy.

^                   # 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
źródło
4

PARI / GP, 27 bajtów

n->eulerphi(n-1-primepi(n))
Charles
źródło
4

Galaretka , niekonkurująca

7 bajtów Ta odpowiedź jest niekonkurencyjna, ponieważ używa języka, który stanowi datę późniejszą wyzwania.

ÆC_@’ÆṪ

Jak to działa

Æ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
źródło
3

Oktawa, 52 51

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

Edycja: zapisano 1 bajt dzięki Thomasowi Kwa

Wyjaśnienie:

@(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
źródło
3

PARI / GP, 35 bajtów

n->eulerphi(sum(x=2,n,!isprime(x)))
alephalpha
źródło
3

SageMath 26 bajtów

euler_phi(n-1-prime_pi(n))

Działa dobrze nawet dla n=0i n=1dzięki implementacji Sage.

Siema'
źródło
3

Galaretka , 6 bajtów

_ÆC’ÆṪ

Wypróbuj online!

Jest to współpraca między Cairnem coinheringahhing a Mr. Xcoderem na czacie

Wyjaśnienie

_ÆC'ÆṪ ~ Pełny program.

 ÆC ~ Policz liczby pierwsze mniejsze lub równe Z.
_ ~ Odejmij od wejścia.
   „~ Zmniejszenie.
    ÆṪ ~ Funkcja totulowa Eulera.
caird coinheringaahing
źródło
3

Gaia , 5 bajtów

ṗ⁈l(t

Wypróbuj online!

ṗ⁈l (t ~ Pełny program.

 ⁈ ~ Odrzuć elementy, które:
ṗ ~ Są pierwszorzędne.
  l ~ długość.
   (~ Zmniejszenie.
    t ~ Suma Eulera.
Pan Xcoder
źródło
2

MATL , 9 bajtów (niekonkurujące)

Ta odpowiedź nie jest konkurencyjna, ponieważ język jest późniejszy niż wyzwanie.

:Zp~sq_Zp

Używa wersji (10.1.0) języka / kompilatora.

Wypróbuj online!

Wyjaśnienie

:       % 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
źródło
2

GAP, 33 bajtów

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

Number(l,p)liczy, ile elementów lspełnia p. Aby zrekompensować fakt, że 1 nie jest ani liczbą pierwszą, ani złożoną, muszę odjąć od n jeden więcej niż liczbę liczb pierwszych do n. Zamiast robić -1dla dwóch bajtów, zaczynam listę od -2 zamiast 1 lub 2, dodając w ten sposób jeszcze jedną liczbę, która jest uważana za pierwszą przez IsPrimetylko jeden dodatkowy bajt.

Christian Sievers
źródło
2

Python 3.5 - 130 bajtów

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

Jeśli niedopuszczalne jest przekazanie funkcji jako p (n, 0,0), to +3 bajty.

Wykorzystuje to fakt, że używam twierdzenia Wilsona, aby sprawdzić, czy liczba jest złożona i muszę zadzwonić do modułu matematycznego dla funkcji silni. Python 3.5 dodał funkcję gcd do modułu matematycznego.

Pierwsza pętla kodu będzie zwiększać k o jeden, jeśli liczba jest złożona, i zwiększać o 0 w przeciwnym razie. (Chociaż twierdzenie Wilsona dotyczy tylko liczb całkowitych większych niż 1, traktuje 1 jako liczbę pierwszą, więc pozwala nam to wykorzystać).

Druga pętla będzie następnie zapętlać w zakresie liczby kompozytów i zwiększać g tylko wtedy, gdy wartości nie pi i l są pierwszorzędne.

g jest wówczas liczbą wartości mniejszych lub równych liczbie liczb zespolonych mniejszych lub równych n.

Joe Habel
źródło
1

05AB1E , 11 8 bajtów

LDpÈÏg<Õ

Wypróbuj online!

To może być niekonkurencyjne - nie mogę się dowiedzieć, kiedy powstało 05AB1E.

Jak to działa

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
kosmiczne śmieci
źródło
1

Pyt , 6 bajtów

řṗ¬Ʃ⁻Ț

Wyjaśnienie:

                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


Wypróbuj online!

mudkip201
źródło
1

APL NARS, 38 bajtów, 19 znaków

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

13π to funkcja totient, a 2π to podstawowa funkcja count <= jej argument. Test

  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
źródło
1

Dodaj ++ , 21 bajtów

L,RþPbL1_dRdVÞ%bLG!!+

Wypróbuj online!

Jak to działa

π¯(n)φ(n)π¯(n)φ(n)

π¯(n)

RþPbL1_

RþPþPbL1_x=π¯(n)

φ(n)

dRdVÞ%bLG!!+

xdRÞ%xxbL

n1nG!!

Tak, naprawdę chciałem wypróbować nowy LaTex


źródło