Wprowadzenie

Prime Funkcja zliczania , znany również jako funkcja Pi , powraca się liczb pierwszych ilości mniejszej niż lub równą x.$\pi(x)$

Wyzwanie

Twój program przyjmie liczbę całkowitą x, którą możesz założyć jako dodatnią, i wyświetli jedną liczbę całkowitą równą liczbie liczb pierwszych mniejszej lub równej x. To wyzwanie dla golfa , więc zwycięzcą zostanie program z najmniejszą liczbą bajtów.

Możesz użyć dowolnego języka, który wybrałeś, pod warunkiem, że istniał przed tym wyzwaniem, ale jeśli język ma wbudowaną funkcję liczenia liczb pierwszych lub funkcję sprawdzania pierwotności (taką jak Mathematica), nie można użyć tej funkcji w kodzie .

Przykładowe dane wejściowe

Wejście:
1
Wyjście:
0

Wejście:
2
Wyjście:
1

Wejście:
5
Wyjście:
3

A000720 - OEIS

05AB1E , 3 bajty

!fg

Zakłada się, że dozwolone są wbudowane czynniki. Wypróbuj online!

Jak to działa

!    Compute the factorial of the input.
 f   Determine its unique prime factors.
  g  Get the length of the resulting list.

Python 2, 45 bajtów

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

Wykorzystuje generator liczb pierwszych Twierdzenia Wilsona . Produkt pśledzi (k-1)!^2i p%kwynosi 1 dla liczb pierwszych i 0 dla liczb niepierwszych.

MATL , 11, 10, 8 , 5 bajtów

:pYFn

Wypróbuj online!

Napisałem wersję, która miała naprawdę fajne wyjaśnienie działania macierzy MATL:

:YF!s1=1

Ale to już nie ma znaczenia. Sprawdź historię zmian, jeśli chcesz ją zobaczyć.

Nowe wyjaśnienie:

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

Trzy bajty zaoszczędzone dzięki genialnemu rozwiązaniu Dennisa

Galaretka , 8 5 bajtów

3 bajty zapisane dzięki @Dennis!

RÆESL

Wypróbuj online!

Port odpowiedzi MATL DJMcMayhem (poprzednia wersja) udoskonalony przez Dennisa.

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

Szablony MediaWiki z ParserFunctions , 220 + 19 = 239 bajtów

{{#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}}}}}}}}}}}}

Aby wywołać szablon:

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

Ułożone w stylu 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}}}}}}}}}}}}

Tylko podstawowy test pierwotności od 2 do n . Numery z trzech szelki wokół nich są zmienne, gdzie {{{1}}}jest n , {{{2}}}to liczba testowany, {{{3}}}jest czynnikiem, który należy sprawdzić.

Perl, 33 bajty

Obejmuje +1 dla -p

Podaj numer wejściowy na STDIN

primecount.pl

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

Daje zły wynik, 0ale to jest OK, operacja poprosiła o wsparcie tylko dla dodatnich liczb całkowitych.

Retina, 31 bajtów

Liczba bajtów zakłada kodowanie ISO 8859-1. Konwertuj dane wejściowe na jednostkowe, generuj zakres od 1do n, każdy w osobnej linii. Dopasuj liczby pierwsze.

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

Wypróbuj online - Wprowadź znacznie większy niż 2800 limit czasu lub brak pamięci.

Referencje:

Generator zasięgu Martina

Główny sprawdzian Martina

Galaretka , 3 bajty

!Æv

Wypróbuj online!

Jak to działa

!Æv  Main link. Argument: n

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

Galaretka , 13 11 10 9 8 7 6 bajtów

Bez
użycia wbudowanych funkcji pierwszych -1 bajt dzięki @miles (użyj tabeli)
-1 bajt dzięki @Dennis (konwertuj z unarnego na zliczanie dzielników)

ḍþḅ1ċ2

TryItOnline
Lub zobacz pierwsze 100 terminów seriin=[1,100], również na TryItOnline

W jaki sposób?

ḍþḅ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)

JavaScript (ES6), 45 43 bajtów

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

Modyfikacja My 36 35 33 bajtów funkcja pierwszości (1 bajt zapisywane @Neil, 2 przez @Arnauld)

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

(Nie mogę tego nigdzie opublikować, ponieważ Czy ten numer jest liczbą pierwszą? Akceptuje tylko pełne programy ...)

Testowy fragment kodu

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

<input type="number" oninput="console.log('f('+this.value+') is '+f(this.value))" value=2>

PowerShell v2 +, 98 bajtów

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

Uwaga: Jest to powolne dla dużych danych wejściowych.

Zasadniczo wyszukiwanie jednostronne z Czy liczba ta jest liczbą pierwszą? , w połączeniu z forpętlą i $j++licznikiem. Trochę dodatkowej logiki z przodu, aby uwzględnić wkłady skrzynek krawędziowych 1oraz 2, ze względu na to, jak słupek ogrodzeniowy działa w forpętlach.

05AB1E , 5 bajtów

Zakłada, że ​​dozwolone są wbudowane czynniki pierwsze.

Kod:

LÒ1ùg

Wyjaśnienie:

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

Wykorzystuje kodowanie CP-1252 . Wypróbuj online!

CJam , 7 bajtów

rim!mF,

Wypróbuj online! Wykorzystuje funkcję faktoryzacji.

Wyjaśnienie:

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

Galaretka , 6 bajtów

Ḷ!²%RS

Wykorzystuje tylko podstawową arytmetykę i twierdzenie Wilsona. Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

Ḷ!²%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.

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

Nie golfił

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

Pyth - 7 6 bajtów

Ponieważ inni używają głównych funkcji faktoryzacji ...

l{sPMS

Pakiet testowy .

Bash + coreutils, 30

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

Ideone.

Bash + coreutils + pakiet gier BSD, 22

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

Ta krótsza odpowiedź wymaga posiadania zainstalowanego pakietu bsdgames: sudo apt install bsdgames.

Pyke, 8 6 bajtów

SmPs}l

Wypróbuj tutaj!

Dzięki Maltysen za nowy algorytm

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

C #, 157 bajtów

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

Pełny program z przypadkami testowymi:

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"));
    }
}

Zaczyna chwilę, gdy przekroczysz 1 milion.

Matlab, 60 bajtów

Kontynuując moje przywiązanie do jednowierszowych funkcji Matlaba. Bez użycia wbudowanej faktoryzacji:

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

Biorąc pod uwagę, że liczba pierwsza yma tylko dwa czynniki [1,y]: liczymy liczby w zakresie, [1,x]który ma tylko dwa czynniki.

Zastosowanie faktoryzacji pozwala na znaczne skrócenie (do 46 bajtów).

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

Wniosek: Muszę przyjrzeć się im golfowym językom: D

Właściwie 10 bajtów

To było najkrótsze rozwiązanie, jakie znalazłem, i które nie napotkało błędów interpretera w TIO. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

;╗r`P╜>`░l

Ungolfing

         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.

Galaretka , 3 bajty

ÆRL

Galaretka ma wbudowaną funkcję zliczania liczb pierwszych ÆCi funkcję sprawdzania liczb pierwszych ÆP, zamiast tego wykorzystuje wbudowaną funkcję generowania liczb pierwszych ÆRi przyjmuje długość L.

Wydaje mi się, że jest to mniej więcej tak graniczne, jak użycie wbudowanych czynników pierwszej generacji, które również zajęłyby 3 bajty !Æv( !czynnikowe, Ævliczby pierwsze)

PHP, 96 92 bajtów

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;

Oszczędność 4 bajtów dzięki Romanowi Gräfowi

Przetestuj online

Nie testowany kod testowy:

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

Przetestuj online

APL (Dyalog Unicode) , 13 bajtów ^SBCS

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

Wypróbuj online!

⍳ d ndices 1…
 N⧽ ∘.| tabela reszty (używając tych dwóch jako osi)
⍳ ɩ ndices 1… N

0+.= suma elementów równa zero (tj. ile dzielników ma każdy)

2+.= suma elementów równa się dwóm (tj. ile jest liczb pierwszych)

Python 3, 40 bajtów

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

Dziwna liczba całkowita k jest liczbą pierwszą, jeśli tylko jeśli 2 ** (k-1) jest zgodne z 1 mod k. Tak więc sprawdzamy tylko ten warunek i dodajemy 1 dla przypadku k = 2.

MATL , 9 bajtów

Pozwala to uniknąć rozkładu pierwszorzędowego. Jego złożoność wynosi O ( n ²).

:t!\~s2=s

Wypróbuj 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

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

Zaoszczędzono 3 5 bajtów dzięki Neilowi:

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

evalmoże uzyskać dostęp do nparametru.
Do eval(...)sprawdza czy njest liczbą pierwszą.

Poprzednie rozwiązania:
liczba bajtów powinna wynosić +2, ponieważ zapomniałem nazwać funkcję f=(potrzebne do rekurencji)

46 + 2 bajty (Zapisane 3 bajty dzięki produktom ETH):

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

50 + 2 bajty:

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

Java 7,102 bajtów

Brutalna siła

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

Nie golfił

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

q 35 bajtów

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

Właściwie 10 bajtów

Jeśli moja pierwsza odpowiedź jest niedozwolona za użycie funkcji generowania liczb pierwszych, oto odpowiedź rezerwowa z twierdzeniem Wilsona. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

R`;D!²%`MΣ

Wypróbuj 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.