Fungsi penghitungan utama

28

pengantar

The Prime Menghitung Function , juga dikenal sebagai Pi fungsi , mengembalikan jumlah bilangan prima kurang dari atau sama dengan x.π(x)

Tantangan

Program Anda akan mengambil bilangan x yang Anda anggap positif, dan menghasilkan bilangan bulat tunggal yang sama dengan jumlah bilangan prima kurang dari atau sama dengan x. Ini adalah tantangan , jadi pemenangnya adalah program dengan byte paling sedikit.

Anda dapat menggunakan bahasa apa pun yang Anda pilih asalkan sudah ada sebelum tantangan ini naik, tetapi jika bahasa tersebut memiliki fungsi penghitungan prime bawaan atau fungsi pemeriksaan primality (seperti Mathematica), fungsi itu tidak dapat digunakan dalam kode Anda .

Contoh Input

Input:
1
Keluaran:
0

Input:
2
Keluaran:
1

Input:
5
Keluaran:
3

A000720 - OEIS

Pavel
sumber
3
Bagaimana dengan fungsi utama terkait lainnya? Misalnya, fungsi "perdana berikutnya"
Luis Mendo
6
bagaimana dengan fungsi faktorisasi utama?
Maltysen
4
Selamat Datang di Programming Puzzles dan Code Golf!
Adnan
6
Seperti yang dikatakan Adnan, selamat datang di PPCG! Untuk tantangan di masa mendatang, izinkan saya merekomendasikan Sandbox tempat Anda dapat memposting tantangan untuk mendapatkan umpan balik dan kritik yang berarti sebelum mempostingnya ke situs utama.
AdmBorkBork
Saya pikir inilah yang dimaksudkan oleh @TheBikingViking untuk terhubung ke: Terkait
mbomb007

Jawaban:

36

05AB1E , 3 byte

!fg

Ini mengasumsikan bahwa built-in faktorisasi diperbolehkan. Cobalah online!

Bagaimana itu bekerja

!    Compute the factorial of the input.
 f   Determine its unique prime factors.
  g  Get the length of the resulting list.
Dennis
sumber
5
Itu sangat pintar!
mbomb007
5
Sial, saya mendapatkan rekt dalam bahasa saya sendiri untuk kedua kalinya haha. +1
Adnan
Mengapa ini bekerja?
Oliver Ni
1
@Oliver Karena faktorial n dapat dibagi oleh semua bilangan bulat 1, ..., n (khususnya, bilangan prima p ≤ n ), dan tidak ada bilangan prima q> n karena tidak dapat dinyatakan sebagai produk dengan angka lebih kecil.
Dennis
10

Python 2, 45 byte

f=lambda n,k=1,p=1:n/k and p%k+f(n,k+1,p*k*k)

Menggunakan generator utama Teorema Wilson . Produk pmelacak (k-1)!^2, dan p%kadalah 1 untuk bilangan prima dan 0 untuk nonprima.

Tidak
sumber
Menghitung faktorial dari bawah ke atas adalah trik yang bagus. +1
ETHproduk
6

MATL , 11, 10, 8 , 5 byte

:pYFn

Cobalah online!

Saya menulis versi yang memiliki penjelasan yang sangat keren tentang cara kerja matriks MATL:

:YF!s1=1

Tapi itu tidak lagi relevan. Periksa riwayat revisi jika Anda ingin melihatnya.

Penjelasan baru:

:p      % Compute factorial(input)
  YF    % Get the exponenents of prime factorization
    n   % Get the length of the array

Tiga byte disimpan berkat solusi jenius Dennis

DJMcMayhem
sumber
Ini lebih pendek untuk menggunakan fungsi "eksponen faktorisasi utama", karena yang satu vectorizes:YF!s1=s
Luis Mendo
@LuisMendo Itu pendekatan yang sama sekali berbeda, jadi silakan lanjutkan dan kirim. (Meskipun jika Anda tidak mau, saya dengan senang hati akan)
DJMcMayhem
Lanjutkan. Saya akan port ke Jelly untuk berlatih :-)
Luis Mendo
5

Jelly , 8 5 byte

3 byte disimpan berkat @Dennis!

RÆESL

Cobalah online!

Port jawaban MATM DJMcMayhem (versi sebelumnya) disempurnakan oleh Dennis.

R          Range of input argument
 ÆE        List of lists of exponents of prime-factor decomposition
   S       Vectorized sum. This right-pads inner lists with zeros
    L      Length of result
Luis Mendo
sumber
1
Koreksi: pelabuhan Luis Mendo: jawaban MATL DJMcMayhem. : P
DJMcMayhem
2
Anda hanya membutuhkan panjang maksimal hasil ÆE, karena setiap eksponen sesuai dengan faktor prima yang berbeda. RÆESLhanya mencapai itu. !ÆELakan lebih pendek.
Dennis
1
@Dennis Terima kasih! Saya telah menggunakan saran pertama. Yang kedua terlalu berbeda, dan pendekatan Anda
Luis Mendo
5

Templat MediaWiki dengan ParserFunctions , 220 + 19 = 239 byte

{{#ifexpr:{{{2}}}+1={{{1}}}|0|{{#ifexpr:{{{3}}}={{{2}}}|{{P|{{{1}}}|{{#expr:{{{2}}}+1}}|2}}|{{#ifexpr:{{{2}}} mod {{{3}}}=0|{{#expr:1+{{P|{{{1}}}|{{#expr:{{{2}}}+1}}|2}}|{{P|{{{1}}}|{{{2}}}|{{#expr:{{{2}}}+1}}}}}}}}}}}}

Untuk memanggil templat:

{{{P|{{{n}}}|2|2}}}

Diatur dalam gaya Lisp:

{{#ifexpr:{{{2}}} + 1 = {{{1}}}|0|
    {{#ifexpr:{{{3}}} = {{{2}}} |
        {{P|{{{1}}}|{{#expr:{{{2}}} + 1}}|2}} |
            {{#ifexpr:{{{2}}} mod {{{3}}} = 0 |
                {{#expr:1 + {{P|{{{1}}}|{{#expr:{{{2}}} + 1}}|2}} |
                {{P|{{{1}}}|{{{2}}}|{{#expr:{{{2}}} + 1}}}}}}}}}}}}

Hanya tes primality dasar dari 2 hingga n . Angka-angka dengan tiga kawat gigi di sekitar mereka adalah variabel, di mana {{{1}}}adalah n , {{{2}}}adalah jumlah yang diuji, {{{3}}}adalah faktor untuk memeriksa.

DuhHello
sumber
5

Perl, 33 byte

Termasuk +1 untuk -p

Berikan nomor input pada STDIN

primecount.pl

#!/usr/bin/perl -p
$_=1x$_;$_=s%(?!(11+)\1+$)%%eg-2

Memberikan hasil yang salah untuk 0tetapi tidak apa-apa, op meminta dukungan untuk bilangan bulat positif saja.

Ton Hospel
sumber
4

Retina, 31 byte

Hitungan byte mengasumsikan penyandian ISO 8859-1. Konversikan input ke unary, buat rentang dari 1ke n, masing-masing pada jalurnya sendiri. Cocokkan bilangan prima.

.*
$*
\B
¶$`
m`^(?!(..+)\1+$)..

Cobalah online - Masukkan jauh lebih besar dari 2800 kali atau kehabisan memori.

Referensi:

Generator jarak Martin

Pemeriksa utama Martin

mbomb007
sumber
4

Jelly , 3 byte

!Æv

Cobalah online!

Bagaimana itu bekerja

!Æv  Main link. Argument: n

!    Compute the factorial of n.
 Æv  Count the number of distinct prime factors.
Dennis
sumber
4

Jelly , 13 11 10 9 8 7 6 byte

Tidak menggunakan fungsi prime
bawaan apa pun -1 byte berkat @miles (gunakan tabel)
-1 byte terima kasih ke @Dennis (konversi dari unary untuk menghitung pembagi)

ḍþḅ1ċ2

TryItOnline
Atau lihat 100 syarat pertama dari seri inin=[1,100], juga di TryItOnline

Bagaimana?

ḍþḅ1ċ2 - Main link: n
 þ     - table or outer product, n implicitly becomes [1,2,3,...n]
ḍ      - divides
  ḅ1   - Convert from unary: number of numbers in [1,2,3,...,n] that divide x
                             (numbers greater than x do not divide x)
    ċ2 - count 2s: count the numbers in [1,2,3,...,n] with exactly 2 divisors
                   (only primes have 2 divisors: 1 and themselves)
Jonathan Allan
sumber
1
Anda bisa mencapai 7 byte %þ`¬Sċ2menggunakan tabel sisa.
mil
1
ḍþḅ1ċ2menghemat satu byte.
Dennis
4

JavaScript (ES6), 45 43 byte

f=(n,x=n)=>n>1&&(--x<2)+(n%x?f(n,x):f(n-1))

Modifikasi fungsi primality 36 35 33 byte saya (1 byte disimpan oleh @Neil, 2 oleh @Arnauld):

f=(n,x=n)=>n>1&--x<2||n%x&&f(n,x)

(Saya tidak dapat memposting ini di mana pun karena Apakah nomor ini utama? Hanya menerima program lengkap ...)

Cuplikan tes

Produksi ETH
sumber
Waw ... butuh beberapa saat bagiku untuk mengerti. Pekerjaan yang baik!
todeale
Sayangnya itu tidak berlaku untuk jawaban Anda tetapi Anda mungkin bisa lolos dengan satu &di tengah fungsi primality Anda.
Neil
3

PowerShell v2 +, 98 byte

param($n)if($j='001'[$n]){}else{for($i=1;$i-lt$n){for(;'1'*++$i-match'^(?!(..+)\1+$)..'){$j++}}}$j

Perhatian: Ini lambat untuk input besar.

Pada dasarnya pencarian berdasarkan unary dari Apakah nomor ini prima? , ditambah dengan forloop dan $j++penghitung. Sedikit logika tambahan di bagian depan untuk memperhitungkan input kasus tepi 1dan 2, karena cara kerja fenceposting di forloop.

AdmBorkBork
sumber
3

05AB1E , 5 byte

Diasumsikan bahwa builtin faktorisasi utama diperbolehkan.

Kode:

LÒ1ùg

Penjelasan:

L      # Get the range [1, ..., input]
 Ò     # Prime factorize each with duplicates
  1ù   # Keep the elements with length 1
    g  # Get the length of the resulting array

Menggunakan pengkodean CP-1252 . Cobalah online!

Adnan
sumber
ÅPgapa yang akan terjadi sekarang, kan?
Magic Gurita Guci
3

CJam , 7 byte

rim!mF,

Cobalah online! Menggunakan fungsi faktorisasi.

Penjelasan:

ri      | read input as integer
  m!    | take the factorial
    mF  | factorize with exponents (one element per prime)
      , | find length
Linus
sumber
3

Jelly , 6 byte

Ḷ!²%RS

Ini hanya menggunakan aritmatika dasar dan teorema Wilson. Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

Ḷ!²%RS  Main link. Argument: n

Ḷ       Unlength; yield [0, ..., n - 1].
 !      Factorial; yield [0!, ..., (n - 1)!].
  ²     Square; yield [0!², ..., (n - 1)!²].
    R   Range; yield [1, ..., n].
   %    Modulus; yield [0!² % 1, ..., (n - 1)!² % n].
        By a corollary to Wilson's theorem, (k - 1)!² % k yields 1 if k is prime
        and 0 if k is 1 or composite.
     S  Sum; add the resulting Booleans.
Dennis
sumber
3

C # 5.0 78 77

int F(int n){int z=n;if(n<2)return 0;for(;n%--z!=0;);return(2>z?1:0)+F(n-1);}

Tidak disatukan

int F(int n)
{
    var z = n;
    if (n < 2) return 0;
    for (; n % --z != 0;) ;
    return F(n - 1) + (2 > z ? 1 : 0);
}
Ariel Bereslavsky
sumber
@ tfbninja ya Anda benar, tapi saya memberikan bagian fungsi saja, yang tidak dikompilasi sendiri
Ariel Bereslavsky
@ tfbninja Sebenarnya, tidak.
Erik the Outgolfer
keren kedengarannya bagus!
FantaC
2

Pyth - 7 6 byte

Karena yang lain menggunakan fungsi faktorisasi prima ...

l{sPMS

Test Suite .

Maltysen
sumber
2

Bash + coreutils, 30

seq $1|factor|egrep -c :.\\S+$

Ideone.


Paket Bash + coreutils + BSD-games, 22

primes 1 $[$1+1]|wc -l

Jawaban pendek ini mengharuskan Anda memiliki bsdgames paket yang diinstal: sudo apt install bsdgames.

Trauma Digital
sumber
2

Pyke, 8 6 byte

SmPs}l

Coba di sini!

Terima kasih kepada Maltysen untuk algoritma baru

SmP    -    map(factorise, input)
   s   -   sum(^)
    }  -  uniquify(^)
     l - len(^)
Biru
sumber
2

C #, 157 byte

n=>{int c=0,i=1,j;bool f;for(;i<=n;i++){if(i==1);else if(i<=3)c++;else if(i%2==0|i%3==0);else{j=5;f=1>0;while(j*j<=i)if(i%j++==0)f=1<0;c+=f?1:0;}}return c;};

Program lengkap dengan uji kasus:

using System;

class a
{
    static void Main()
    {
        Func<int, int> s = n =>
            {
                int c = 0, i = 1, j;
                bool f;
                for (; i <= n; i++)
                {
                    if (i == 1) ;
                    else if (i <= 3) c++;
                    else if (i % 2 == 0 | i % 3 == 0) ;
                    else
                    {
                        j = 5;
                        f = 1 > 0;
                        while (j * j <= i)
                            if (i % j++ == 0)
                                f = 1 < 0;
                        c += f ? 1 : 0;
                    }
                }
                return c;
            };

        Console.WriteLine("1 -> 0 : " + (s(1) == 0 ? "OK" : "FAIL"));
        Console.WriteLine("2 -> 1 : " + (s(2) == 1 ? "OK" : "FAIL"));
        Console.WriteLine("5 -> 3 : " + (s(5) == 3 ? "OK" : "FAIL"));
        Console.WriteLine("10 -> 4 : " + (s(10) == 4 ? "OK" : "FAIL"));
        Console.WriteLine("100 -> 25 : " + (s(100) == 25 ? "OK" : "FAIL"));
        Console.WriteLine("1,000 -> 168 : " + (s(1000) == 168 ? "OK" : "FAIL"));
        Console.WriteLine("10,000 -> 1,229 : " + (s(10000) == 1229 ? "OK" : "FAIL"));
        Console.WriteLine("100,000 -> 9,592 : " + (s(100000) == 9592 ? "OK" : "FAIL"));
        Console.WriteLine("1,000,000 -> 78,498 : " + (s(1000000) == 78498 ? "OK" : "FAIL"));
    }
}

Mulai mengambil beberapa saat setelah Anda pergi di atas 1 juta.

Yodle
sumber
2

Matlab, 60 byte

Melanjutkan lampiran saya ke fungsi Matlab satu baris. Tanpa menggunakan faktorisasi bawaan:

f=@(x) nnz(arrayfun(@(x) x-2==nnz(mod(x,[1:1:x])),[1:1:x]));

Mengingat bahwa bilangan prima yhanya memiliki dua faktor [1,y]: kita menghitung angka dalam rentang [1,x]yang hanya memiliki dua faktor.

Menggunakan factorisation memungkinkan untuk pemendekan yang signifikan (turun ke 46 byte).

g=@(x) size(unique(factor(factorial(x))),2);

Kesimpulan: Perlu melihat ke dalam mereka bahasa golf: D

ptev
sumber
2

Sebenarnya 10 byte

Ini adalah solusi terpendek yang saya temukan yang tidak mengalami bug juru bahasa di TIO. Saran bermain golf diterima. Cobalah online!

;╗r`P╜>`░l

Tidak melakukanolf

         Implicit input n.
;╗       Duplicate n and save a copy of n to register 0.
r        Push range [0..(n-1)].
`...`░   Push values of the range where the following function returns a truthy value.
  P        Push the a-th prime
  ╜        Push n from register 0.
  >        Check if n > the a-th prime.
l        Push len(the_resulting_list).
         Implicit return.
Sherlock9
sumber
2

Jelly , 3 byte

ÆRL

Jelly memiliki fungsi penghitungan prima built-in, ÆCdan fungsi pengecekan prima ÆP, ini menggunakan fungsi pembangkit prima built-in, ÆRdan memakan waktu lama L.

Saya kira ini adalah tentang batas menggunakan faktorisasi bawaan bawaan, yang juga akan memakan waktu 3 byte !Æv( !faktorial, Ævhitung faktor prima)

Jonathan Allan
sumber
2

PHP, 96 92 byte

for($j=$argv[1]-1;$j>0;$j--){$p=1;for($i=2;$i<$j;$i++)if(is_int($j/$i))$p=0;$t+=$p;}echo $t;

Disimpan 4 byte berkat Roman Gräf

Tes online

Kode pengujian tidak digabungkan:

$argv[1] = 5;

for($j=$argv[1]-1;$j>0;$j--) {
    $p=1;
    for($i=2;$i<$j;$i++) {
        if(is_int($j/$i)) {
            $p=0;
        }
    }
    $t+=$p;
}
echo $t;

Tes online

Mario
sumber
Mengapa Anda menggunakan isInt(...)?1:0dan bukan hanyaisInt(...)
Roman Gräf
@ RomanGräf Terima kasih, Anda benar. Saya meninggalkan ternary setelah banyak pelapukan kode, dan itu sangat jelas sehingga saya tidak bisa melihatnya ...
Mario
2

APL (Dyalog Unicode) , 13 byte SBCS

2+.=0+.=⍳∘.|⍳

Cobalah online!

ɩ ndices 1…
 N⧽ ∘.| tabel sisa (menggunakan keduanya sebagai sumbu)
ɩ ndices 1 ... N

0+.= jumlah elemen yang sama dengan nol (yaitu berapa banyak pembagi masing-masing memiliki)

2+.= jumlah elemen sama dengan dua (yaitu berapa banyak bilangan prima yang ada)

Adm
sumber
2

Python 3, 40 byte

f=lambda n:1if n<1else(2**n%n==2)+f(n-1)

Bilangan bulat ganjil adalah bilangan prima jika hanya 2 ** (k-1) kongruen dengan 1 mod k. Jadi, kami hanya memeriksa kondisi ini dan menambahkan 1 untuk kasus k = 2.

Sandeep Silwal
sumber
2 ** n% n == 2 tidak cukup sebagai ujian utama
RosLuP
@RosLuP Itulah sebabnya kasus dasar dari n == 0 harus menambahkan 1 (untuk menjelaskan kasus n = 2).
Sandeep Silwal
2 ** n% n == 2 tidak cukup secara umum ... Ada banyak (tidak terbatas dalam apa yang saya ingat) angka di mana 2 ^ n% n = 2 yang bukan bilangan prima
RosLuP
Misalnya 341 = 11 * 31 tetapi (2 ^ 341) mod 341 == 2
RosLuP
@ RosLuP: Ah ok ya, saya mencarinya. Angka-angka ini disebut Fermat Psuedoprimes tetapi mereka tampaknya sangat jarang: P
Sandeep Silwal
2

MATL , 9 byte

Ini menghindari dekomposisi faktor prima. Kompleksitas adalah O ( n ²).

:t!\~s2=s

Cobalah online!

:     % Range [1 2 ... n] (row vector)
t!    % Duplicate and transpose into a column vector
\     % Modulo with broadcast. Gives matrix in which entry (i,j) is i modulo j, with
      % i, j in [1 2 ... n]. A value 0 in entry (i,j) means i is divisible by j
~     % Negate. Now 1 means i is divisible by j
s     % Sum of each column. Gives row vector with the number of divisors of each j
2=    % Compare each entry with 2. A true result corresponds to a prime
s     % Sum
Luis Mendo
sumber
1

JavaScript (ES6), 50 + 2 46 + 2 43 byte

Disimpan 3 5 byte berkat Neil:

f=n=>n&&eval(`for(z=n;n%--z;);1==z`)+f(n-1)

evaldapat mengakses nparameter.
The eval(...)memeriksa apakah nperdana.


Solusi sebelumnya:
Hitungan byte harus +2 karena saya lupa memberi nama fungsi f=(diperlukan untuk rekursi)

46 + 2 byte (Disimpan 3 byte berkat produk ETH):

n=>n&&eval(`for(z=n=${n};n%--z;);1==z`)+f(n-1)

50 + 2 byte:

n=>n&&eval(`for(z=${n};${n}%--z&&z;);1==z`)+f(n-1)
Hedi
sumber
1
Setidaknya di browser saya, evaldapat mengakses nparameter ke fungsi Anda (yang Anda lupa namanya, dikenakan biaya 2 byte; ada baiknya mengetahui bahwa saya bukan satu-satunya yang membuat kesalahan itu) yang menghemat 5 byte.
Neil
@ Neil aku tidak tahu eval. Diuji dengan firefox, chrome dan edge, itu bekerja untuk saya. Penjelasannya adalah eval () diuraikan dalam konteks pernyataan . Dua contoh: a=12;f=b=>eval('a + 5');f(8)menampilkan 17dan a=12;f=a=>eval('a + 5');f(8)menampilkan 13.
Hedi
1

Java 7.102 byte

Paksaan

int f(int n){int i=2,j=2,c=1,t=0;for(;i<=n;j=2,c+=t==1?1:0,i++)for(;j<i;t=i%j++==0?j=i+1:1);return c;}

Tidak disatukan

int f(int n){
int i=2,j=2,c=1,t=0;
for(;i<=n;j=2,c+=t==1?1:0,i++)
    for(;j<i;)
        t=i%j++==0?j=i+1:1;
    return c;
 }
Numberknot
sumber
Ini saat ini memberikan hasil yang salah untuk input 1. Saat ini kembali 1bukan 0. Anda dapat memperbaiki hal ini dengan baik mengubah return c;ke return n<2?0:c;atau mengubah ,c=1,ke ,c=n<2?0:1,.
Kevin Cruijssen
1

q 35 byte

{sum 1=sum'[0=2_' a mod\: a:til x]}
Ruben taylor
sumber
1

Sebenarnya 10 byte

Jika jawaban Sebenarnya saya yang pertama tidak diizinkan untuk menggunakan fungsi penghasil prima, berikut adalah jawaban cadangan menggunakan teorema Wilson. Saran bermain golf diterima. Cobalah online!

R`;D!²%`MΣ

Cobalah online

         Implicit input n.
R        Push range [1..n]
`...`M   Map the following function over the range. Variable k.
  ;        Duplicate k.
  D        Decrement one of the copies of k.
  !²       Push ((k-1)!)².
  %        Push ((k-1)!)² % k. This returns 1 if k is prime, else 0.
Σ        Sums the result of the map, adding all the 1s that represent primes, 
          giving the total number of primes less than n.
         Implicit return.
Sherlock9
sumber