Prime counting function

Question

Introduction

The Prime Counting Function, also known as the Pi function \$\pi(x)\$, returns the amount of primes less than or equal to x.

Challenge

Your program will take an integer x which you can assume to be positive, and output a single integer equal to the amount of primes less than or equal to x. This is a code-golf challenge, so the winner will be the program with the fewest bytes.

You may use any language of your choosing provided that it existed before this challenge went up, but if the language has a built-in prime-counting function or a primality checking function (such as Mathematica), that function cannot be used in your code.

Example Inputs

Input:
1
Output:
0

Input:
2
Output:
1

Input:
5
Output:
3

A000720 - OEIS

Answer 1

Java 7,102 bytes

Brute force

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

Answer 2

q 35 bytes

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

Answer 3

Actually, 10 bytes

If my first Actually answer is disallowed for using a prime-generating function, here is a backup answer using Wilson's theorem. Golfing suggestions welcome. Try it online!

R`;D!²%`MΣ

Try it 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.

Answer 4

PARI/GP, 15 bytes

n->#factor(n!)~

Take the factorial and count its unique prime factors.

Answer 5

Actually, 3 bytes

This uses a prime factorization function, which may or may not be allowed after the OP clarifies. Golfing suggestions welcome. Try it online!

!yl

Ungolfing

     Implicit input n.
!    Push n factorial.
 y   Push a list of all of the positive prime factors of n! (every prime < n)
  l  Take the length of that list of primes.
     Implicit return.

Answer 6

Racket 60 bytes

(require math)(λ(n)(length(filter prime?(range 1(+ 1 n)))))

Testing:

(require math)
(define f
    (λ(n) (length (filter prime? (range 1 (+ 1 n)))))
)

(f 1)
(f 2)
(f 3)
(f 5)

Output:

0
1
2
3

Answer 7

Perl 6, 31 bytes

{+grep {$_%%none 2..^$_},2..$_}

Try it online!

Answer 8

Python 3, 40 bytes

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

An odd integer k is prime if an only if 2**(k-1) is congruent to 1 mod k. Thus, we just check for this condition and add 1 for the case of k=2.

Answer 9

(pure) BASH, 138 bytes

Look, Mom!
No preloaded prime tables, no prime related builtins, not even a division or plultimication!

a=2
l=0
while((a<=$1));do if((b[a]))
then((c=b[a]));else((c=a,l++));fi;((d=a+c))
while((b[d]));do((d+=c));done
((b[d]=c,a++));done;echo $l

Eating the pudding:

$ for i in 1 2 3 11033 ; do bash fsoe-primecounter-in-bash $i ; done
0
1
2
1337

Ok, probably looping while looking at candidates modulo all possible divisors would have been shorter in "pure BASH" too but we've seen those loops at least 1001 times now.

This solution builds its own prime table on the fly and so is bearably fast even in "pure BASH".

Answer 10

Pyt, 3 bytes

řṗƩ

Explanation:

ř         Push [1,2,...,input]
 ṗ        Elementwise isPrime(k)
  Ʃ       Sum of array (autoconverts booleans to 0/1)

Try it online!

Answer 11

Pyth, 6 bytes

l{P.!Q

Explanation follows:

   .!Q Factorial of input
  P    List primes of factorial with multiplicity
 {     Remove duplicates formed by said multiplicity
l      Length of deduplicated list

Answer 12

APL NARS, 150 bytes

∇r←g n;h;i;k
i←0⋄h←1+⍳n-1⋄→B
A:k←i⊃h⋄h←k∪(0≠k∣h)/h
B:→A×⍳(⍴h)≥i+←1
r←⍴h
∇

this would be the "Crivello di Eratostene" or something as that.

If h=2..n

In the first iteration of the loop eliminate each multiple of 2 in h except 2

in the second iteration of the loop eliminate each multiple of 3 in h except 3

...

return the number of final element of h.(in h primes return ⍴h)

  g¨1 2 5
0  1  3 
  g 20000
2262

As note negative for the question: There would be a range limit for the arg of the function; something as 1..20000 and each answer would indicate the range the argument has to be for to be safe to pass to the function (without one seg fault in the code, without one memory insufficient for the program, without one incorrect value return as result )

Answer 13

Add++, 17 bytes

L,RB*f0b]@bLA1=!*

Try it online!

Answer 14

Kotlin, 85 bytes

{n:Int->var r=0
for(i in 2..n){var t=1
for(p in 2..i/2)if(i%p==0){t--
break}
r+=t}
r}

Try it online!

Try lambda for first time as saved 16 bytes.

Kotlin, 101 bytes

fun c(n:Int):Int{var r=0
for(i in 2..n){var t=1
for(p in 2..i/2)if(i%p==0){t--
break}
r+=t}
return r}

Try it online!

Answer 15

Haskell, 46 42 bytes

p n=sum[mod(product[1..i-1]^2)i|i<-[1..n]]

Try it online!

Answer 16

Python 3, 197 165 bytes

Removed the need for the import math by checking every divisor of i besides i itself, though mathematically only checking up to the square root is required.

def c(x):
    p=0
    for i in range(2,x+1):
        P=1
        for d in range(1,i):
            if i%d==0 and d!=1:
                P=0
        p+=1*P
    return p

Original:

import math
def c(x):
    p=0
    for i in range(2,x+1):
        P=1
        for d in range(1,round(math.sqrt(i))+1):
            if i%d==0 and d!=1:
                P=0
        p+=1*P
    return p

Answer 17

Vyxal l, 2 bytes

¡Ǐ

Try it Online! - test cases only

This is the same as the 3 byte answer below except the length is taken by the l flag rather than an L element.

Vyxal, 3 bytes

¡ǏL

Try it Online!

¡  # Factorial
Ǐ  # Prime factorization - list of distinct prime factors
L  # Length of that list

Direct port of Dennis's 05AB1E solution, which is the accepted answer, so one would infer that it meets the challenge's specifications.

The element † could be considered a "prime-counting function", even though it counts the distinct prime factors of the input, not the primes less than or equal to the input. The solution using that built-in is 2 bytes:

¡†

Try it Online!

¡  # Factorial
†  # Number of distinct prime factors

Vyxal, 9 bytes

ɾ⟑‹¡²$%;∑

Try it Online!

With no factorization built-ins, instead using Wilson's theorem:

ɾ  # Inclusive One Range (from 1 to input)
⟑  # Apply lambda to each individual list item:
‹  # Subtract 1
¡  # Factorial
²  # Square
$  # Swap 
%  # Modulo - this will be (n-1)!² % n
;  # Close lambda
∑  # Sum

With the r flag this is 8 bytes: Try it Online!
With the rs flags this is 6 bytes: Try it Online!

Answer 18

Stax, 4 bytes

Ü:÷/

Run and debug it

Same approach as many other answers. This is a packed stax program which unpacks to the following 5 bytes:

|F:F%

Run and debug it

Explanation

|F    # factorial of input
  :F  # distinct prime factors
    % # length

Answer 19

Japt, 6 bytes

Êk â Ê

Try it

Êk â Ê     :Implicit input of integer
Ê          :Factorial
 k         :Prime factors
   â       :Deduplicate
     Ê     :Length

Answer 20

Python 2, 55 bytes

n=input()
s=p=i=1
while i<n:p*=i*i;i+=1;s+=p%i
print~-s

Try it online!

A programification of the below. The Python 3 equivalent is 62 bytes.

Note that although xnor's recursive answer outgolfs this at 45 bytes, it cannot handle an input of 999 or greater, due to Python's recursion limit: Try it online! - this limit can be increased, though: Try it online!

This 55 byte solution can go well beyond that. For example, all inputs up to 3000: Try it online!

Python 3.8+, 57 54 bytes

lambda n,p=1:sum([(p:=p*i*i)%-~i for i in range(1,n)])

Try it online! / Attempt This Online!

A lambdafication of the below, taking advantage of the := operator.

Although xnor's recursive answer outgolfs this at 46 bytes when ported to Python 3, it still can't handle an input of 999 or greater: Try it online! - this limit can be increased: Attempt This Online!

Python, 59 bytes

def P(n):
 s=p=i=1
 while i<n:p*=i*i;i+=1;s+=p%i
 return~-s

Try it online! - Python 2
Try it online! - Python 3

Based on miles's answer to "Is it a super-prime?".

This exploits Wilson's theorem and Python's arbitrary precision integers to count primes. At each iteration of the loop, with \$i\in[2,n]\$, it calculates \${(i-1)^2}!\pmod i\$. This \$\equiv 1\$ when \$i\$ is prime and \$\equiv 0\$ otherwise. The squaring is done to compensate for the fact that \$4\$ is the only exception, with \$(4-1)!\equiv 2\pmod 4\$, but \$(4-1)^2!\equiv 0\pmod 4\$. Note that squaring also changes the modulus from \$-1\$ to \$1\$ for prime \$i\$.

If not for the exception at i=4, we could have done

while i<n:p*=i;i+=1;s+=-p%i

For 1 byte less, because Python returns a positive result when taking a negative number modulo a positive number.