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

05AB1E, 3 bytes

!fg


This assumes that factorization built-ins are allowed. Try it online!

How it works

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

• That's really clever! Commented Sep 23, 2016 at 21:01
• Damn, I'm getting rekt in my own language for the second time haha. +1 Commented Sep 23, 2016 at 21:24
• Why does this work? Commented Oct 23, 2016 at 5:36
• @Oliver Because the factorial of n is divisible by all integers 1, ..., n (in particular, the primes p ≤ n), and by no other prime q > n since it cannot be expressed as a product of smaller numbers. Commented Oct 23, 2016 at 5:38
• ÅP is a built-in for getting the list of all prime numbers $≤n$. Not that it saves any bytes, but…¯\_(ツ)_/¯ Commented Mar 30, 2021 at 0:39

Python 2, 45 bytes

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


Uses the Wilson's Theorem prime generator. The product p tracks (k-1)!^2, and p%k is 1 for primes and 0 for nonprimes.

• Calculating the factorial from the bottom up is a great trick. +1 Commented Sep 23, 2016 at 23:38

MATL, 11, 10, 8, 5 bytes

:pYFn


Try it online!

I wrote a version that had a really cool explanation of how MATL's matrices work:

:YF!s1=1

But it's no longer relevant. Check out the revision history if you want to see it.

New explanation:

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


Three bytes saved thanks to Dennis's genius solution

• It's shorter to use the function "exponents of prime factorization", because that one vectorizes: YF!s1=s Commented Sep 23, 2016 at 20:18
• @LuisMendo That's a totally different approach, so feel free to go ahead and post it. (Although if you don't want to, I happily would) Commented Sep 23, 2016 at 20:20
• Go ahead. I'll port that to Jelly to practice :-) Commented Sep 23, 2016 at 20:22

Jelly, 8 5 bytes

3 bytes saved thanks to @Dennis!

RÆESL


Try it online!

Port of DJMcMayhem's MATL answer (former version) refined by 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

• Correction: port of Luis Mendo's: DJMcMayhem's MATL answer. :P Commented Sep 23, 2016 at 20:26
• You only need the maximal length of the results of ÆE, as each exponent corresponds to a different prime factor. RÆESL achieves just that. !ÆEL would be even shorter. Commented Sep 23, 2016 at 21:43
• @Dennis Thanks! I've used the first suggestion. The second one is too different, and is your approach Commented Sep 23, 2016 at 21:54

MediaWiki templates with 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}}}}}}}}}}}}


To call the template:

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


Arranged in Lisp style:

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


Just a basic primality test from 2 to n. The numbers with three braces around them are the variables, where {{{1}}} is n, {{{2}}} is the number being tested, {{{3}}} is the factor to check.

Perl, 33 bytes

Includes +1 for -p

Give the input number on STDIN

primecount.pl

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


Gives the wrong result for 0 but that's OK, the op asked for support for positive integers only.

Retina 0.8.2, 31 22 bytes

Byte count assumes ISO 8859-1 encoding.

.+
$* (?!(..+)\1+$).\B


Try it online - Input much larger than 2800 either times out or runs out of memory.

References:

Martin's range generator

Martin's prime checker

Jelly, 3 bytes

!Æv


Try it online!

How it works

!Æv  Main link. Argument: n

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


Jelly, 13 11 10 9 8 7 6 bytes

Using no built-in prime functions whatsoever
-1 byte thanks to @miles (use a table)
-1 byte thanks to @Dennis (convert from unary to count up the divisors)

ḍþḅ1ċ2


TryItOnline
Or see the first 100 terms of the series n=[1,100], also at TryItOnline

How?

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

• You can get to 7 bytes %þ¬Sċ2 using a table of remainders. Commented Sep 23, 2016 at 22:53
• ḍþḅ1ċ2 saves a byte. Commented Sep 24, 2016 at 19:05

JavaScript (ES6), 45 43 bytes

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


A modification of my 36 35 33-byte primality function (1 byte saved by @Neil, 2 by @Arnauld):

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


(I can't post this anywhere because Is this number a prime? only accepts full programs...)

Test snippet

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>

• Waw...it took me a while to understand. Nice job! Commented Sep 24, 2016 at 9:09
• Sadly it doesn't apply to your answer but you can probably get away with one & in the middle of your primality function.
– Neil
Commented Sep 24, 2016 at 17:50

05AB1E, 5 bytes

Assumes that prime factorization builtins are allowed.

Code:

LÒ1ùg


Explanation:

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


Uses the CP-1252 encoding. Try it online!

• ÅPg is what it'd be now, right? Commented Jan 18, 2018 at 17:55

Jelly, 6 bytes

Ḷ!²%RS


This uses only basic arithmetic and Wilson's theorem. Try it online! or verify all test cases.

How it works

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

• @tfbninja yes you right, but I gave the function part only, which does not compile by it's own Commented Jan 16, 2018 at 21:27
• @tfbninja Actually, it's not. Commented Jan 17, 2018 at 13:09
• cool sounds good!
– qqq
Commented Jan 17, 2018 at 15:41

Regex (Perl / Java / PCRE), 32 bytes

((?=(\2?+x*?(?!(xx+)\3+$))xx)x)*  Try it online! - Perl Try it online! - Java Try it online! - PCRE Takes its input in unary, as a string of x characters whose length represents the number. Returns its output as the length of the match.  # tail = N = input value; no anchor needed, as every value returns a match # Count the number of primes <= N, from the largest to the smallest prime. ( # J = 0 (?= # \2 starts at zero, and on each subsequent iteration, contains the difference # N-P-(J-1) where P is the previously found prime, and J is the running total of # our prime count. ( \2?+ # Start from the previous value of \2, atomically so that it # can't be backtracked and started again from zero if the # following fails to match. This will make tail = P-1, where # P is the previously found prime. x*? # Advance as little as necessary to make the following match, # and add this to \2, while subtracting it from tail. (?!(xx+)\3+$)  # Assert tail is not composite; note that this needs to be
# inside group \2 for it to work in PCRE1 and older versions of
# PCRE2, which atomicize groups that have nested backreferences
)
xx                 # Assert tail is prime by eliminating the false positives 0, 1
)
x   # J += 1; tail -= 1
)*      # Iterate zero or more times, until there are no more smaller primes
# Return J as our match


Regex (Pythonregex / Ruby), 41 39 bytes

((?=(?=(\3?))(\2x*?(?!(xx+)\4+$))xx)x)*  Try it online! - Python import regex Try it online! - Ruby This is a port of the Perl/Java/PCRE regex to flavors that have no support for nested backreferences. Python's built-in re module does not even support forward backreferences, so for Python this requires regex.  # tail = N = input value; no anchor needed, as every value returns a match # Count the number of primes <= N, from the largest to the smallest prime. ( # J = 0 (?= # \2 starts at zero, and on each subsequent iteration, contains the difference # N-P-(J-1) where P is the previously found prime, and J is the running total of # our prime count. (?=(\3?)) # \2 = \3 (or 0 if \3 is unset), to make up for the lack of # nested backreferences ( \2 # Start from the previous value of \3 (as copied into \2). # This will make tail = P-1, where P is the previously found # prime. x*? # Advance as little as necessary to make the following match, # and add this to \3, while subtracting it from tail. (?!(xx+)\4+$)  # Assert tail is not composite; note that this needs to be
# inside group \3 for it to work in PCRE1 and older versions of
# PCRE2, which atomicize groups that have nested backreferences
)
xx                 # Assert tail is prime by eliminating the false positives 0, 1
)
x   # J += 1; tail -= 1
)*      # Iterate zero or more times, until there are no more smaller primes
# Return J as our match


((?=((?>\2?)x*?(?!(xx+)\3+$))xx)x)*  Try it online! This is a direct port of the Perl/Java/PCRE regex. Regex (.NET), 35 bytes ^(?=(x*?(?!(xx+)\2+$)x)*x)(?<-1>x)*


Try it online!

This uses the .NET feature of balanced groups to do the counting. It does not return a value for zero, but doing so only requires +1 byte (36 bytes):

^(?=(x*?(?!(xx+)\2+$)x)*x|)(?<-1>x)*  Try it online! ^ # tail = N = input number (?= ( x*? # Advance as little as necessary to make the following match (?!(xx+)\3+$)  # Assert tail is not composite
x              # Eliminate the false primality positive of 0, and advance forward
# so that the next prime can be found (if we didn't do this, the
# regex engine would exit the loop due to a zero-width match)
)*                 # Every time this loop matches an iteration, the capture group 1
# match is pushed onto the stack. This (balanced groups) is how we
# count the number of primes.
x                  # Eliminate the false primality positive of 1
|                      # Allow us to return a value of 0 for N=0
)
(?<-1>x)*              # Pop all of the group 2 captures off the stack, doing head += 1
# for each one. This gives us our return value match.


I strongly suspect this function is impossible to implement in ECMAScript regex, even with the addition of (?*) or (?<=) / (?<!). There doesn't seem to be room to multiplex the count and the current prime into a single tail variable, but I don't know if this can be proved.

Only one variable can be modified within a loop, such that must decrease by at least 1 on every step – and only $$\O(n)\$$ space is available; no variable may contain a value larger than $$\n\$$, and the language has no concept of arrays (although it is possible to take them as immutable input), only scalar variables (i.e. capture groups and the cursor position).

So it would seem that calculating this function would require $$\O({n^2\over log(n)})\$$ scratch space, to multiplex the iteration count and current prime into a single number. While multiple loops in a row would be able to get closer to $$\\pi(n)\$$ than a single loop, the number of such loops could only be a constant; it seems that it would need to be able to grow with $$\n\$$ to be able to actually asymptotically calculate $$\\pi(n)\$$. And a nested loop would still have to distill all the information gained by its innermost loop into a single number $$\\le n\$$.

But these things are just indications and vague evidence, not a proof. I have set a bounty regarding this open question.

Pyth - 7 6 bytes

Since others are using prime factorization functions...

l{sPMS


Bash + coreutils, 30

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


Ideone.

Bash + coreutils + BSD-games package, 22

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


This shorter answer requires that you have the bsdgames package installed: sudo apt install bsdgames.

Pyke, 8 6 bytes

SmPs}l


Try it here!

Thanks to Maltysen for new algorithm

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


Full program with test cases:

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


Starts to take awhile once you go above 1 million.

Matlab, 60 bytes

Continuing my attachment to one-line Matlab functions. Without using a factorisation built-in:

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


Given that a prime y has only two factors in [1,y]: we count the numbers in the range [1,x] which have only two factors.

Using factorisation allows for significant shortening (down to 46 bytes).

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


Conclusion: Need to look into them golfing languages :D

Actually, 10 bytes

This was the shortest solution I found that didn't run into interpreter bugs on TIO. Golfing suggestions welcome. Try it online!

;╗rP╜>░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.


Jelly, 3 bytes

ÆRL


Jelly has a built-in prime counting function, ÆC and a prime checking function, ÆP, this instead uses a built-in prime generating function, ÆR and takes the length L.

I guess this is about as borderline as using prime factorisation built-ins, which would also take 3 bytes with !Æv (! factorial, Æv count prime factors)

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;  Saved 4 bytes thanks to Roman Gräf Test online Ungolfed testing code: $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;  Test online • Why do you use isInt(...)?1:0 and not just isInt(...) Commented Sep 25, 2016 at 18:09 • @RomanGräf Thanks, you are right. I left the ternary after a lot of code semplification, and that was so obvious that I couldn't see it... Commented Sep 25, 2016 at 20:12 Java 8, 95 84 bytes z->{int c=0,n=2,i,x;for(;n<=z;c+=x>1?1:0)for(x=n++,i=2;i<x;x=x%i++<1?0:x);return c;}  Explanation: Try it online. z->{ // Method with integer parameter and integer return-type int c=0, // Start the counter at 0 n=2, // Starting prime is 2 i,x; // Two other temp integers for(;n<=z; // Loop (1) as long as n is smaller than or equal to the input z c+=x>1?1:0) // and increase the counter if we've came across a prime // (if x is larger than 0, it means the current n is a prime) for(x=n++,i=2;i<x;x=x%i++<1?0:x); // Determine if the next integer in line is a prime by setting x // (and increase n by 1 afterwards) // End of loop (1) (implicit / single-line body) return c; // Return the resulting counter } // End of method  APL (Dyalog Unicode), 13 bytesSBCS 2+.=0+.=⍳∘.|⍳  Try it online! ⍳ɩndices 1…N ⧽ ∘.| remainder-table (using those two as axes) ⍳ɩndices 1…N 0+.= the sum of the elements equal to zero (i.e. how many dividers does each have) 2+.= the sum of the elements equal to two (i.e. how many primes are there) • Another approach {⍴(⊢~∘.×⍨)1↓⍳⍵} Commented Mar 31, 2021 at 5:28 • @AndrewOgden Ooh, that actually comes out shorter: (≢⊢~∘.×⍨)1↓⍳ ― Do you want to post that, it being a completely different approach? – Adám Commented Mar 31, 2021 at 5:49 • I would, but it's not my algorithm. youtu.be/Gsj_7tFtODk?t=600 Commented Mar 31, 2021 at 7:00 • @AndrewOgden I know. I came up with it in '97 :-) Go ahead and post! – Adám Commented Mar 31, 2021 at 7:04 • Lol, you're a legend. Commented Mar 31, 2021 at 7:23 MATL, 9 bytes This avoids prime-factor decomposition. Its complexity is O(n²). :t!\~s2=s  Try it 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  APL (Dyalog Unicode), 12 bytes (≢⊢~∘.×⍨)1↓⍳ ≢ ⍝ tally ⊢~ ⍝ index values not in matrix of composite numbers ∘.×⍨ ⍝ outer product of positive integers with themselves 1↓⍳ ⍝ range from 1–n less the first element  h/t @adám Try it online! C (clang), 49 bytes p(n,i){for(i=n;--i&&n%i;);return--n?p(n)+!--i:0;}  Assumes n is positive. Try it online! Thunno, $$\ 4 \log_{256}(96) \approx \$$ 3.29 bytes FAFL  Attempt This Online! Port of Dennis's 05AB1E answer. Explanation F # Push the factorial of the input AF # Get the unique prime factors L # Push the length of the list  JavaScript (ES6), 50+246+2 43 bytes Saved 3 5 bytes thanks to Neil: f=n=>n&&eval(for(z=n;n%--z;);1==z)+f(n-1)  eval can access the n parameter. The eval(...) checks if n is prime. Previous solutions: Byte count should be +2 because I forgot to name the function f= (needed for recursion) 46+2 bytes (Saved 3 bytes thanks to 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)

• At least on my browser, eval can access the n parameter to your function (which you forgot to name, costing you 2 bytes; it's good to know that I'm not the only one who makes that mistake) which saves you 5 bytes.
– Neil
Commented Sep 24, 2016 at 17:47
• @Neil I didn't know for eval. Tested with firefox, chrome and edge it worked for me. The explanation is eval() parses in statement context. Two examples: a=12;f=b=>eval('a + 5');f(8) displays 17 and a=12;f=a=>eval('a + 5');f(8) displays 13`.
– Hedi
Commented Sep 24, 2016 at 19:11