# Prime counting function

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

• What about other prime-related functions? For example, "next prime" funciton Commented Sep 23, 2016 at 20:09
• what about prime factorization functions? Commented Sep 23, 2016 at 20:13
• Welcome to Programming Puzzles and Code Golf! Commented Sep 23, 2016 at 20:35
• As Adnan said, welcome to PPCG! For future challenges, let me recommend the Sandbox where you can post a challenge to get meaningful feedback and critique before posting it to the main site. Commented Sep 23, 2016 at 20:44
• I think this is what @TheBikingViking meant to link to: Related Commented Sep 23, 2016 at 20:52

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

• This is currently giving an incorrect result for input 1. It currently returns 1 instead of 0. You can fix this by either changing return c; to return n<2?0:c; or changing ,c=1, to ,c=n<2?0:1,. Commented May 12, 2017 at 14:27

# q 35 bytes

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


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


# PARI/GP, 15 bytes

n->#factor(n!)~


Take the factorial and count its unique prime factors.

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


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

• If (require math) is required for your program to work, you need to include it in your byte count. Commented May 11, 2017 at 15:41

# Perl 6, 31 bytes

{+grep {$_%%none 2..^$_},2..$_}  Try it online! ## 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. • 2**n % n==2 is not enough as primaly test – user58988 Commented Jan 18, 2018 at 16:42 • @RosLuP That is why the base case of n==0 should add 1 (to account for the n=2 case). Commented Jan 19, 2018 at 0:02 • 2**n % n==2 is not enough in general... Exist many (infinite in what I would remember) numbers where 2^n%n=2 that are not primes – user58988 Commented Jan 19, 2018 at 7:48 • For example 341=11*31 but ( 2^341) mod 341==2 – user58988 Commented Jan 19, 2018 at 8:44 • @RosLuP: Ah ok yes, I looked it up. These numbers are called Fermat Psuedoprimes but they appear to be quite rare :P Commented Jan 19, 2018 at 22:55 # (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". # Pyt, 3 bytes řṗƩ  Explanation: ř Push [1,2,...,input] ṗ Elementwise isPrime(k) Ʃ Sum of array (autoconverts booleans to 0/1)  Try it online! • So one can use isprime right? – user58988 Commented Jan 18, 2018 at 16:45 # 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  # 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 ) # Add++, 17 bytes L,RB*f0b]@bLA1=!*  Try it online! # 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! # Haskell, 46 42 bytes p n=sum[mod(product[1..i-1]^2)i|i<-[1..n]]  Try it online! # 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  • Welcome to Code Golf! You can golf this quite a bit by removing some whitespace, and I think you're allowed to use a lambda instead of a function if that'd be shorter. Commented Apr 7, 2021 at 20:13 # Vyxall, 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!

# 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


# Japt, 6 bytes

Êk â Ê


Try it

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


# 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)])


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

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.

# Thunno 2L, 2 bytes

wƑ


Try it online!

wƑ  # Implicit input