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

var QUESTION_ID=63710,OVERRIDE_USER=12914;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

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.

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

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.

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

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

Mathematica, 24 byte

EulerPhi[#-PrimePi@#-1]&

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.

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.

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.

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

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

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.

PARI / GP, 27 byte

n->eulerphi(n-1-primepi(n))

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.

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

PARI / GP, 35 byte

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

SageMath 26 byte

euler_phi(n-1-prime_pi(n))

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

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.

Gaia , 5 byte

ṗ⁈l(t

Cobalah online!

ṗ⁈l (t ~ Program lengkap.

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

Ohm v2 , 7 byte

³³Pl-‹φ

Cobalah online!

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

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.

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.

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!

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

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!

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

Tambahkan ++ , 21 byte

L,RþPbL1_dRdVÞ%bLG!!+

Cobalah online!

Bagaimana itu bekerja

$\overline\pi(n)$$\varphi(n)$$\overline\pi(n)$$\varphi(n)$

$\overline\pi(n)$

RþPbL1_

RþPþPbL1_$x = \overline\pi(n)$

$\varphi(n)$

dRdVÞ%bLG!!+

$x$dRÞ%$x$$x$bL

$n - 1$$n$G!!

_{Ya, saya benar-benar ingin mencoba LaTex baru}