Hitung Phi (bukan Pi)

73

Tidak, maksud saya bukan ϕ = 1.618...dan π = 3.14159.... Maksud saya fungsinya .

  • φ (x) adalah jumlah bilangan bulat kurang dari atau sama dengan xyang relatif prima x.
  • π (x) adalah jumlah bilangan prima yang kurang dari atau sama dengan x.
  • Katakanlah "bukan pi" adalah π̅ (x) dan tetapkan itu sebagai jumlah komposit yang kurang dari atau sama dengan x.

Tugas

Dengan bilangan bulat yang benar-benar positif x, hitung φ (π̅ (x)) . Skor dalam byte.

Contohnya

Setiap baris terdiri dari input (dari 1 hingga 100, inklusif) dan output terkait dipisahkan oleh spasi.

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

Gunakan tautan ini untuk menghitung output yang diharapkan untuk input apa pun. Juga, daftar input dan output x <= 1000disediakan di sini pada pastebin . (Dihasilkan dengan program Minkolang ini .)


Papan peringkat

Berikut ini adalah Stack Snippet untuk menghasilkan leaderboard biasa dan gambaran umum pemenang berdasarkan bahasa.

Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:

## Language Name, N bytes

di mana Nukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Misalnya:

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

Jika Anda ingin memasukkan beberapa angka dalam tajuk Anda (mis. Karena skor Anda adalah jumlah dari dua file atau Anda ingin membuat daftar hukuman penterjemah secara terpisah), pastikan bahwa skor sebenarnya adalah angka terakhir di tajuk:

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

Anda juga dapat membuat tautan nama bahasa yang kemudian akan muncul di cuplikan papan peringkat:

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

El'endia Starman
sumber
Apakah ada batasan ukuran input?
lirtosiast
4
Apakah pertanyaan ini merupakan penghargaan untuk pengguna PhiNotPi ?
primo
24
@rimo Mengapa Anda berpikir begitu?
Mego
2
@ Primo: Itu terinspirasi oleh namanya, dan pastinya sebuah permainan kata-kata, tapi bukan penghormatan kepadanya.
El'endia Starman
1
@ edc65: Ya, ternyata begitu , seperti yang saya ketahui kemarin.
El'endia Starman

Jawaban:

27

GS2 , 12 10 byte

V@'◄l.1&‼l

Kode sumber menggunakan pengkodean CP437 . Cobalah online!

Uji coba

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

Bagaimana itu bekerja

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
sumber
25
Nama file lebih panjang dari program.
Floris
43

Regex (.NET), 122 113 byte

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

Dengan asumsi input dan output dalam kondisi unary, dan output diambil dari pertandingan utama regex.

Rincian regex:

  • ^(?=((?=.*$(?<=^(\3+(.+.))(.*?(?>(.\4)?)))).)+(.*)) menghitung π̅ (x) dan menangkap sisa string dalam menangkap grup 6 untuk pernyataan di bagian kedua.

    • .*$set pointer ke ujung string sehingga kita memiliki seluruh bilangan xdalam satu arah.
    • (?<=^(\3+(.+.))(.*?(?>(.\4)?))) cocok dari kanan ke kiri dan memeriksa nomor komposit dengan menggeser dari x ke 0.
      • (.*?(?>(.\4)?))adalah "variabel" yang dimulai dari 0 pada iterasi pertama dan berlanjut dari angka pada iterasi sebelumnya dan loop hingga x. Karena angka komposit terkecil adalah 4, (.\4)?tidak pernah gagal untuk mencocokkan jika menangkap grup 4 tersedia.
      • ^(\3+(.+.))memeriksa apa yang ditinggalkan oleh "variabel" di atas (yaitu x - "variable") apakah itu adalah angka komposit.
  • ((?=.*(?=\6$)(?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?)))).)+menghitung φ (π̅ (x)), dengan membatasi operasi kiri-ke-kanan dengan (?=\6$).

    • .*(?=\6$)mengatur pointer ke posisi π̅ (x). Mari kita tunjukkan y = π̅ (x).
    • (?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?))) cocok dari kanan ke kiri dan memeriksa prime relatif dengan pengulangan dari (y - 1) ke 0
      • (.+?(?>\9?)) adalah "variabel" yang dimulai dari 1 pada iterasi pertama dan berlanjut dari angka pada iterasi sebelumnya dan loop hingga y
      • (?!(.+.)\8*(?=\6$)(?<=^\8+))cocok dari kiri ke kanan 1 dan memeriksa apakah "variabel" dan y relatif prima.
        • (.+.)\8*(?=\6$) mengambil pembagi "variabel" yang lebih besar dari 1, dan efek sampingnya adalah kita memiliki bilangan bulat y di sebelah kiri.
        • (?<=^\8+) memeriksa apakah pembagi "variabel" juga merupakan pembagi y.

1 Dalam. NET, lihat-depan menetapkan arah ke LTR alih-alih mengikuti arah saat ini; look-behind mengatur arah ke RTL alih-alih membalikkan arah.

Uji regex di RegexStorm .

Revisi 2 menjatuhkan grup yang tidak menangkap dan menggunakan grup atom alih-alih sintaksis bersyarat.

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
sumber
24
Pak, kamu gila.
RK.
9
Dia punya sentuhan Zalgo saya pikir.
curiousdannii
11
Dan sekarang Anda memiliki dua masalah. (Serius tidak tahu Anda bisa melakukan hal semacam ini dengan Regex ...)
Darrel Hoffman
21

J, 15 14 byte

5 p:<:-_1 p:>:

Ini adalah kata kerja monadik diam-diam. Cobalah online dengan J.js .

Bagaimana itu bekerja

                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
sumber
14
saya dapat penjelasan haz? : P
anOKsquirrel
23
i haz menambahkan penjelasan
Dennis
5
Saya akan mengatakan bahwa saya telah meningkatkan ini karena memiliki banyak smiley, tetapi teks mengatakan kepada saya untuk menghindari mereka :(
Doddy
@ Dennis: Balasan pertamamu membuatku tertawa, terima kasih untuk itu!
Mehrdad
19

Serius , 27 byte

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

Yay, saya mengalahkan CJam! Cobalah online

Penjelasan ( amerujuk ke atas tumpukan, bmengacu pada kedua-dari-atas):

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

Catatan: sejak posting jawaban ini, saya telah menambahkan fungsi pi dan phi ke Serius. Berikut adalah jawaban yang tidak bersaing dengan fungsi-fungsi tersebut:

,;▓1-@-▒

Penjelasan (beberapa perintah dialihkan untuk tidak tumpang tindih dengan yang lain):

,    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
sumber
1
@Dennis Anda SERIUS OUTGOLFED OUTGOLFED!
TanMath
Tolong jangan bilang kamu tahu ini di bagian atas kepala kamu ..
DividedByZero
1
GJ mengalahkan CJam =)
flawr
14

Julia, 52 50 byte

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

Ini menciptakan fungsi tanpa nama yang menerima dan integer dan mengembalikan integer. Untuk menyebutnya, berikan nama, mis f=x->....

Tidak Disatukan:

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.
sumber
Gunakan sumalih-alih countuntuk menyimpan beberapa karakter. Ini sedikit frustasi, meskipun - cara lain untuk menghitung bilangan prima,, sum(isprime,1:x)persis sama panjangnya endof(primes(x)).
Glen O
1
@ GlenO Terima kasih atas sarannya, tetapi sumgagal untuk koleksi kosong sambil countmengembalikan 0. Dengan demikian sumtidak akan menghasilkan hasil yang diinginkan x<4.
Alex A.
8

Mathematica, 24 byte

EulerPhi[#-PrimePi@#-1]&
LegionMammal978
sumber
2
Tentu saja Mathematica memiliki semua ini dibangun di ...
bertepuk tangan
@ConfusedMr_C Jelas :) Namun, itu tidak didiskualifikasi, karena alasan yang jelas: perangkat lunak matematika tidak dapat mengalahkan permainan golf dalam tugas kombinatorial sederhana :)
yo '
@ConfusedMr_C PhiNotPi@#&: 11 byte: P
LegionMammal978
8

Pyth, 14 byte

JlftPTSQ/iLJJ1

Demonstrasi , Penguji

Kami menghitung komposit menggunakan filter sederhana, mengambil panjangnya, dan menyimpannya J. Kemudian, kami mengambil gcd dari Jsetiap angka hingga J, dan menghitung berapa hasil yang sama dengan 1.

isaacg
sumber
7

Minkolang 0,11 , 12 byte (TIDAK kompetitif)

Jawaban ini BUKAN kompetitif. Saya menerapkan pi dan phi sebagai built-in sebelum saya memposting pertanyaan, yang memberi saya keuntungan yang tidak adil. Saya memposting ini hanya untuk mereka yang tertarik dengan bahasa ini.

nd9M-1-9$MN.

Coba di sini.

Penjelasan

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
sumber
2
Saya tidak berpikir menerbitkan jawaban yang tidak valid adalah ide yang bagus ...
yeti
20
Selama mereka memiliki disclaimer, saya tidak berpikir ada yang salah dengan itu. Ini sebenarnya cukup umum untuk tantangan yang lebih tua.
Dennis
4
@yeti: Secara teknis, ini tidak valid. Fitur-fitur yang digunakan di sini semuanya diimplementasikan sebelum tantangan diposting. Saya hanya mendiskualifikasi karena saya menunda memposting tantangan sampai dua fitur tertentu diimplementasikan (yang saya gunakan untuk menghasilkan daftar contoh, secara tidak sengaja).
El'endia Starman
1
Sama. Saya sering melakukan ini ketika 𝔼𝕊𝕄𝕚𝕟 terus diperbarui.
Mama Fun Roll
6

CJam, 28 byte

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

Cobalah biola ini dalam juru bahasa CJam atau verifikasi semua kasus uji sekaligus .

Bagaimana itu bekerja

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
sumber
Aku mencoba "memverifikasi semua kasus" link dan punya ini: 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111. Apakah itu benar?
El'endia Starman
Ya, itu memeriksa bahwa menerapkan kode ke kolom kiri (input) sama dengan kolom kanan (keluaran).
Dennis
5
saya dapat penjelasan haz pada dis1?
anOKsquirrel
9
@anOKsquirrel i haz menjelaskan 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
sumber
2
Saya pikir Anda dapat menyimpan 2 byte dengan menghapus spasi di antara range(n) ifdan])) if
DankMemes
3
Mengingat kemampuan Golf Python yang relatif rendah (karena persyaratan ruang kosong, dll.) Ini cukup mengesankan!
felixphew
@DankMemes, terima kasih atas tipnya!
wnnmaw
5

Retina , 48 byte

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

Cobalah online!

Penjelasan

.+
$*

Konversikan input ke unary.

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

Hitung bilangan komposit tidak lebih besar dari input dengan menghitung seberapa sering kita dapat mencocokkan string yang terdiri dari setidaknya dua pengulangan faktor minimal 2.

.+
$*

Konversikan ke unary lagi.

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

Hitung φ dengan menghitung dari berapa banyak posisi tidak mungkin untuk menemukan faktor (minimal 2) akhiran dari posisi itu yang juga merupakan faktor awalan (jika kita menemukan faktor seperti itu maka ini i <= nberbagi faktor dengan nOleh karena itu tidak coprime untuk itu). Pada .akhirnya memastikan bahwa kita tidak menghitung nol (yang mana kita tidak dapat menemukan faktor minimal 2).

Martin Ender
sumber
5

Regex (.NET), 88 86 byte

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

Cobalah online! (Sebagai program Retina.)

Menggunakan I / O yang sama dengan jawaban n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ , yaitu input unary dan cocok dengan substring dari panjang hasil.

Dimungkinkan untuk mempersingkat ini lebih jauh dengan mengganti satu atau kedua kelompok penyeimbang dengan referensi ke depan.

Alternatif pada jumlah byte yang sama:

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

Ada juga beberapa alternatif untuk paruh pertama, misalnya menggunakan lookahead negatif daripada yang positif untuk bilangan komposif, atau menggunakan kondisional di sana juga.

Penjelasan

Saya akan berasumsi bahwa Anda memiliki pemahaman dasar tentang menyeimbangkan grup , tetapi singkatnya, menangkap grup di .NET adalah tumpukan (jadi setiap kali Anda menggunakan kembali grup penangkap, tangkapan baru didorong di atas) dan (?<-x>...)mengeluarkan tangkapan dari tumpukan x. Itu sangat membantu untuk menghitung hal-hal.

^                   # 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
sumber
4

PARI / GP, 27 byte

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

Jelly , tidak bersaing

7 byte Jawaban ini tidak bersaing, karena menggunakan bahasa yang mengatasi tantangan.

ÆC_@’ÆṪ

Bagaimana itu bekerja

Æ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
sumber
3

Oktaf, 52 51

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

Sunting: disimpan 1 byte berkat Thomas Kwa

Penjelasan:

@(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
sumber
3

PARI / GP, 35 byte

n->eulerphi(sum(x=2,n,!isprime(x)))
alephalpha
sumber
3

SageMath 26 byte

euler_phi(n-1-prime_pi(n))

Bekerja dengan baik bahkan untuk n=0dan n=1, berkat implementasi Sage.

yo'
sumber
3

Jelly , 6 byte

_ÆC’ÆṪ

Cobalah online!

Ini adalah kolaborasi antara caird coinheringahhing dan Mr. Xcoder dalam obrolan

Penjelasan

_ÆC'ÆṪ ~ Program lengkap.

 ÆC ~ Hitung bilangan prima kurang dari atau sama dengan Z.
_ ~ Kurangi dari input.
   '~ Penurunan.
    ÆṪ ~ fungsi total Euler.
caird coinheringaahing
sumber
3

Gaia , 5 byte

ṗ⁈l(t

Cobalah online!

ṗ⁈l (t ~ Program lengkap.

 ⁈ ~ Tolak elemen yang:
ṗ ~ Unggul.
  l ~ Panjangnya.
   (~ Pengurangan.
    t ~ jumlah Euler.
Tuan Xcoder
sumber
2

MATL , 9 byte (tidak bersaing)

Jawaban ini tidak bersaing, karena bahasa memposting tantangan.

:Zp~sq_Zp

Menggunakan versi (10.1.0) dari bahasa / kompiler.

Cobalah online!

Penjelasan

:       % 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
sumber
2

GAP, 33 Bytes

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

Number(l,p)menghitung berapa banyak elemen dari lmemuaskan p. Untuk mengimbangi fakta bahwa 1 bukan prima atau komposit, saya harus mengurangi dari satu lebih dari jumlah bilangan prima hingga n. Alih-alih melakukan -1dua byte, saya memulai daftar dengan -2 bukan 1 atau 2, sehingga menambahkan satu nomor lagi yang dianggap prima oleh IsPrimehanya satu byte tambahan.

Sievers Kristen
sumber
2

Python 3.5 - 130 byte

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

Jika tidak dapat diterima untuk melewati fungsi sebagai p (n, 0,0) maka +3 byte.

Ini mengambil keuntungan dari fakta bahwa saya menggunakan teorema Wilson untuk memeriksa apakah suatu bilangan adalah gabungan dan harus memanggil ke dalam modul matematika untuk fungsi faktorial. Python 3.5 menambahkan fungsi gcd ke dalam modul matematika.

Loop pertama dari kode akan bertambah satu per satu jika angkanya komposit dan bertambah 0 dengan cara lain. (Meskipun teorema Wilson hanya berlaku untuk bilangan bulat lebih besar dari 1, itu memperlakukan 1 sebagai bilangan prima, jadi memungkinkan kita untuk mengeksploitasi ini).

Loop kedua kemudian akan mengulangi rentang jumlah komposit dan kenaikan g hanya ketika nilai bukan pi dan l adalah co-prime.

g kemudian jumlah nilai kurang dari atau sama dengan jumlah bilangan komposit kurang dari atau sama dengan n.

Joe Habel
sumber
2

Python 3 + sympy , 59 58 byte

* -1 byte dengan mengganti compositepi(k)dengan k+~primepi(k).

lambda k:totient(k+~primepi(k))
from sympy.ntheory import*

Cobalah online!

Tuan Xcoder
sumber
1

05AB1E , 11 8 byte

LDpÈÏg<Õ

Cobalah online!

Ini mungkin tidak bersaing - saya tidak bisa mengetahui kapan 05AB1E dibuat.

Bagaimana itu bekerja

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
sampah luar angkasa
sumber
1

Pyt , 6 byte

řṗ¬Ʃ⁻Ț

Penjelasan:

                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


Cobalah online!

mudkip201
sumber
1

APL NARS, 38 byte, 19 karakter

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

13π adalah fungsi totient dan 2π adalah fungsi prime count <= argumennya. Uji

  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
sumber
1

Tambahkan ++ , 21 byte

L,RþPbL1_dRdVÞ%bLG!!+

Cobalah online!

Bagaimana itu bekerja

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

π¯(n)

RþPbL1_

RþPþPbL1_x=π¯(n)

φ(n)

dRdVÞ%bLG!!+

xdRÞ%xxbL

n1nG!!

Ya, saya benar-benar ingin mencoba LaTex baru


sumber