Introdução

A função de contagem primária , também conhecida como função Pi $\pi(x)$ , retorna a quantidade de números primos menor ou igual a x.

Desafio

Seu programa pegará um número inteiro x que você pode assumir como positivo e produzirá um número inteiro igual à quantidade de números primos menor ou igual a x. Este é um desafio de código-golfe , portanto, o vencedor será o programa com o menor número de bytes.

Você pode usar qualquer idioma de sua escolha, desde que existisse antes desse desafio, mas se o idioma tiver uma função de contagem primária incorporada ou uma função de verificação de primalidade (como o Mathematica), essa função não poderá ser usada no seu código .

Exemplo de entradas

Entrada:
1
Saída:
0

Entrada:
2
Saída:
1

Entrada:
5
Saída:
3

A000720 - OEIS

05AB1E , 3 bytes

!fg

Isso pressupõe que os built-ins de fatoração são permitidos. Experimente online!

Como funciona

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

Python 2, 45 bytes

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

Usa o gerador principal do Teorema de Wilson . O produto prastreia (k-1)!^2e p%ké 1 para números primos e 0 para não primos.

MATL , 11, 10, 8 , 5 bytes

:pYFn

Experimente online!

Eu escrevi uma versão que tinha uma explicação muito legal de como as matrizes do MATL funcionam:

:YF!s1=1

Mas não é mais relevante. Confira o histórico de revisões, se você quiser vê-lo.

Nova explicação:

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

Três bytes salvos graças à solução genial de Dennis

Geléia , 8 5 bytes

3 bytes salvos graças ao @Dennis!

RÆESL

Experimente online!

Porto da resposta MATL do DJMcMayhem (versão anterior) refinada por 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

Modelos do MediaWiki com ParserFunctions , 220 + 19 = 239 bytes

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

Para chamar o modelo:

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

Organizados em estilo 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}}}}}}}}}}}}

Apenas um teste básico de primalidade de 2 a n . Os números com três chaves ao redor são as variáveis, onde {{{1}}}é n , {{{2}}}é o número que está sendo testado, {{{3}}}é o fator a ser verificado.

Perl, 33 bytes

Inclui +1 para -p

Dê o número de entrada no STDIN

primecount.pl

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

Dá o resultado errado, 0mas tudo bem, o op pediu suporte apenas para números inteiros positivos.

Retina, 31 bytes

A contagem de bytes assume a codificação ISO 8859-1. Converta a entrada em unário, gere o intervalo de 1para n, cada um em sua própria linha. Combine os números primos.

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

Experimente online - Entrada muito maior que 2800 atinge o tempo limite ou fica sem memória.

Referências:

Martin's range generator

Verificador principal de Martin

Gelatina , 3 bytes

!Æv

Experimente online!

Como funciona

!Æv  Main link. Argument: n

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

Gelatina , 13 11 10 9 8 7 6 bytes

Usando nenhuma função primária integrada
-1 byte graças a @miles (use uma tabela)
-1 byte graças a @Dennis (converta de unário para contar os divisores)

ḍþḅ1ċ2

TryItOnline
Ou veja os 100 primeiros termos da sérien=[1,100], também em TryItOnline

Quão?

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

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

Uma modificação da minha função de primalidade 36 35 33 bytes (1 byte salvo por @Neil, 2 por @Arnauld):

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

(Não consigo postar isso em nenhum lugar porque esse número é primo? Só aceita programas completos ...)

Snippet de teste

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 bytes

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

Cuidado: Isso é lento para entradas grandes.

Basicamente, a pesquisa unária de Esse número é primo? , juntamente com um forloop e um $j++contador. Um pouco de lógica adicional na frente para explicar as entradas de casos extremos 1e 2, devido à maneira como a vedação funciona nos forloops.

05AB1E , 5 bytes

Supõe que os componentes principais de fatoração são permitidos.

Código:

LÒ1ùg

Explicação:

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

Usa a codificação CP-1252 . Experimente online!

CJam , 7 bytes

rim!mF,

Experimente online! Usa uma função de fatoração.

Explicação:

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

Gelatina , 6 bytes

Ḷ!²%RS

Isso usa apenas aritmética básica e o teorema de Wilson. Experimente online! ou verifique todos os casos de teste .

Como funciona

Ḷ!²%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);}

Ungolfed

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

Pitão - 7 6 bytes

Como outros estão usando funções de fatoração primárias ...

l{sPMS

Conjunto de Teste .

Bash + coreutils, 30

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

Ideone.

Pacote Bash + coreutils + BSD-games, 22

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

Esta resposta mais curto requer que você tenha o pacote bsdgames instalado: sudo apt install bsdgames.

Pyke, 8 6 bytes

SmPs}l

Experimente aqui!

Agradecimentos a Maltysen pelo novo algoritmo

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

C #, 157 bytes

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

Programa completo com casos de teste:

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

Começa a demorar um pouco quando você ultrapassa 1 milhão.

Matlab, 60 bytes

Continuando meu apego às funções Matlab de uma linha. Sem usar uma fatoração integrada:

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

Dado que um primo ypossui apenas dois fatores [1,y]: contamos os números no intervalo [1,x]que possuem apenas dois fatores.

O uso da fatoração permite um encurtamento significativo (até 46 bytes).

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

Conclusão: É necessário olhar para eles idiomas de golfe: D

Na verdade, 10 bytes

Essa foi a solução mais curta que encontrei e não encontrou erros de intérprete no TIO. Sugestões de golfe são bem-vindas. Experimente 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.

Geléia , 3 bytes

ÆRL

O Jelly possui uma função de contagem primária incorporada ÆCe uma função de verificação primária, que ÆP, em vez disso, usa uma função geradora primária incorporada ÆRe leva o comprimento L.

Eu acho que isso é tão limítrofe quanto usar built-ins de fatoração primária, o que também levaria 3 bytes com !Æv( !fatorial, Ævfatores primários de contagem)

PHP, 96 92 bytes

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;

Guardado 4 bytes graças a Roman Gräf

Teste on-line

Código de teste ungolfed:

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

Teste on-line

APL (Dyalog Unicode) , ^{SBCS de} 13 bytes

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

Experimente online!

⍳ Ɩ ndices 1 ... N
 ⧽ ∘.| restante-tabela (usando os dois como eixos)
⍳ ɩ ndices 1 ... N

0+.= a soma dos elementos igual a zero (ou seja, quantos divisores cada um possui)

2+.= a soma dos elementos igual a dois (ou seja, quantos primos existem)

Python 3, 40 bytes

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

Um número inteiro ímpar k é primo se apenas se 2 ** (k-1) for congruente a 1 mod k. Assim, basta verificar esta condição e adicionar 1 para o caso de k = 2.

MATL , 9 bytes

Isso evita a decomposição do fator primo. Sua complexidade é O ( n ²).

:t!\~s2=s

Experimente 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 bytes

Economizou 3 5 bytes graças a Neil:

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

evalpode acessar o nparâmetro
As eval(...)verificações sen é primo.

Soluções anteriores:
contagem de bytes deve ser +2 porque esqueci de nomear a funçãof= (necessária para recursão)

46 + 2 bytes (economizados 3 bytes graças a ETHproductions):

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

50 + 2 bytes:

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

Java 7.102 bytes

Força bruta

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

Ungolfed

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 bytes

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

Na verdade, 10 bytes

Se minha primeira resposta Realmente não é permitida por usar uma função de geração primária, aqui está uma resposta alternativa usando o teorema de Wilson. Sugestões de golfe são bem-vindas. Experimente online!

R`;D!²%`MΣ

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