Introducción

La función de recuento de primos , también conocida como la función Pi , devuelve la cantidad de primos menor o igual que x.$\pi(x)$

Reto

Su programa tomará un entero x que puede suponer que es positivo y generará un solo entero igual a la cantidad de primos menor o igual a x. Este es un desafío de código de golf , por lo que el ganador será el programa con la menor cantidad de bytes.

Puede usar cualquier idioma de su elección siempre que existiera antes de que este desafío surgiera, pero si el idioma tiene una función de conteo primo incorporada o una función de comprobación de primalidad (como Mathematica), esa función no se puede usar en su código .

Entradas de ejemplo

Entrada:
1
Salida:
0

Entrada:
2
Salida:
1

Entrada:
5
Salida:
3

A000720 - OEIS

05AB1E , 3 bytes

!fg

Esto supone que los factores integrados de factorización están permitidos. Pruébalo en línea!

Cómo 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)

Utiliza el generador principal del teorema de Wilson . El producto prastrea (k-1)!^2, y p%kes 1 para primos y 0 para no primos.

MATL , 11, 10, 8 , 5 bytes

:pYFn

Pruébalo en línea!

Escribí una versión que tenía una explicación genial de cómo funcionan las matrices de MATL:

:YF!s1=1

Pero ya no es relevante. Consulte el historial de revisiones si desea verlo.

Nueva explicación:

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

Tres bytes guardados gracias a la genial solución de Dennis

Jalea , 8 5 bytes

¡3 bytes guardados gracias a @Dennis!

RÆESL

Pruébalo en línea!

Puerto de la respuesta MATL de DJMcMayhem (versión 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

Plantillas MediaWiki con 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 llamar a la plantilla:

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

Dispuesto en 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}}}}}}}}}}}}

Solo una prueba de primalidad básica de 2 a n . Los números con tres llaves alrededor son las variables, donde {{{1}}}es n , {{{2}}}es el número que se está probando, {{{3}}}es el factor a verificar.

Perl, 33 bytes

Incluye +1 para -p

Dar el número de entrada en STDIN

primecount.pl

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

Da el resultado incorrecto 0pero está bien, el operador solicitó soporte solo para enteros positivos.

Retina, 31 bytes

El recuento de bytes asume la codificación ISO 8859-1. Convierta la entrada a unario, genere el rango de 1a n, cada uno en su propia línea. Une los primos.

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

Pruébelo en línea : la entrada es mucho mayor que 2800, ya sea tiempo de espera o se queda sin memoria.

Referencias

Generador de rango de Martin

El inspector principal de Martin

Jalea , 3 bytes

!Æv

Pruébalo en línea!

Cómo 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

Sin utilizar funciones primarias incorporadas de ningún tipo
-1 byte gracias a @miles (use una tabla)
-1 byte gracias a @Dennis (convertir de unario para contar los divisores)

ḍþḅ1ċ2

TryItOnline
O vea los primeros 100 términos de la serien=[1,100], también en TryItOnline

¿Cómo?

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

Una modificación de mi función de primalidad de 36 35 33 bytes (1 byte guardado por @Neil, 2 por @Arnauld):

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

(No puedo publicar esto en ningún lado porque ¿Es este número primo? Solo acepta programas completos ...)

Fragmento de prueba

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

Precaución: Esto es lento para entradas grandes.

Básicamente la búsqueda unaria de ¿Es este número un primo? , junto con un forbucle y un $j++contador. Una pequeña lógica adicional en el frente para tener en cuenta la entrada de casos extremos 1y 2, debido a cómo funciona la valla en los forbucles.

05AB1E , 5 bytes

Asume que se permiten las incorporaciones de factorización prima.

Código:

LÒ1ùg

Explicación:

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

Utiliza la codificación CP-1252 . Pruébalo en línea!

CJam , 7 bytes

rim!mF,

Pruébalo en línea! Utiliza una función de factorización.

Explicación:

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

Jalea , 6 bytes

Ḷ!²%RS

Esto usa solo aritmética básica y el teorema de Wilson. Pruébalo en línea! o verificar todos los casos de prueba .

Cómo 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);}

Sin golf

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 bytes

Dado que otros están utilizando funciones de factorización prima ...

l{sPMS

Test Suite .

Bash + coreutils, 30

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

Ideona

Bash + coreutils + paquete de juegos BSD, 22

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

Esta respuesta más corta requiere que tenga instalado el paquete bsdgames: sudo apt install bsdgames.

Pyke, 8 6 bytes

SmPs}l

Pruébalo aquí!

Gracias a Maltysen por el nuevo 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 con casos de prueba:

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

Comienza a tomar un tiempo una vez que superas el millón.

Matlab, 60 bytes

Continuando mi apego a las funciones de una línea de Matlab. Sin utilizar una factorización incorporada:

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

Dado que un primo ysolo tiene dos factores [1,y]: contamos los números en el rango [1,x]que tienen solo dos factores.

El uso de la factorización permite un acortamiento significativo (hasta 46 bytes).

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

Conclusión: Necesidad de examinarlos idiomas de golf: D

En realidad, 10 bytes

Esta fue la solución más corta que encontré que no se encontró con errores de interpretación en TIO. Sugerencias de golf bienvenidas. Pruébalo en línea!

;╗r`P╜>`░l

No golfista

         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.

Jalea , 3 bytes

ÆRL

Jelly tiene una función de recuento de cebado integrada ÆCy una función de verificación de cebado ÆP; en su lugar, utiliza una función de generación de cebado incorporada ÆRy toma la longitud L.

Supongo que esto es casi tan limítrofe como el uso de factores integrados primos de factorización, que también tomaría 3 bytes con !Æv( !factorial, Ævfactores primos de recuento)

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 gracias a Roman Gräf

Prueba en línea

Código de prueba sin golf:

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

Prueba en línea

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

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

Pruébalo en línea!

⍳ d ndices 1 ... N
 table ∘.| resto-tabla (usando esos dos como ejes)
⍳ ɩ ndices 1 ... N

0+.= la suma de los elementos igual a cero (es decir, cuántos divisores tiene cada uno)

2+.= la suma de los elementos igual a dos (es decir, cuántos primos hay)

Python 3, 40 bytes

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

Un entero impar k es primo si solo si 2 ** (k-1) es congruente con 1 mod k. Por lo tanto, solo verificamos esta condición y agregamos 1 para el caso de k = 2.

MATL , 9 bytes

Esto evita la descomposición de factores primos. Su complejidad es O ( n ²).

:t!\~s2=s

Pruébalo en línea!

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

Guardado 3 5 bytes gracias a Neil:

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

evalPuede acceder al nparámetro.
El eval(...)cheques si nes primo.

Soluciones anteriores: el
recuento de bytes debería ser +2 porque olvidé nombrar la función f=(necesaria para la recursividad)

46 + 2 bytes (Guardado 3 bytes gracias 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

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

Sin golf

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

En realidad, 10 bytes

Si mi primera respuesta en realidad no está permitida por usar una función generadora principal, aquí hay una respuesta de respaldo usando el teorema de Wilson. Sugerencias de golf bienvenidas. Pruébalo en línea!

R`;D!²%`MΣ

Pruébalo en línea

         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.