28
\$\begingroup\$

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

\$\endgroup\$
  • 3
    \$\begingroup\$ What about other prime-related functions? For example, "next prime" funciton \$\endgroup\$ – Luis Mendo Sep 23 '16 at 20:09
  • 6
    \$\begingroup\$ what about prime factorization functions? \$\endgroup\$ – Maltysen Sep 23 '16 at 20:13
  • 4
    \$\begingroup\$ Welcome to Programming Puzzles and Code Golf! \$\endgroup\$ – Adnan Sep 23 '16 at 20:35
  • 6
    \$\begingroup\$ 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. \$\endgroup\$ – AdmBorkBork Sep 23 '16 at 20:44
  • \$\begingroup\$ I think this is what @TheBikingViking meant to link to: Related \$\endgroup\$ – mbomb007 Sep 23 '16 at 20:52

41 Answers 41

35
\$\begingroup\$

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.
\$\endgroup\$
  • 5
    \$\begingroup\$ That's really clever! \$\endgroup\$ – mbomb007 Sep 23 '16 at 21:01
  • 5
    \$\begingroup\$ Damn, I'm getting rekt in my own language for the second time haha. +1 \$\endgroup\$ – Adnan Sep 23 '16 at 21:24
  • \$\begingroup\$ Why does this work? \$\endgroup\$ – Oliver Ni Oct 23 '16 at 5:36
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Dennis Oct 23 '16 at 5:38
10
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Calculating the factorial from the bottom up is a great trick. +1 \$\endgroup\$ – ETHproductions Sep 23 '16 at 23:38
6
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ It's shorter to use the function "exponents of prime factorization", because that one vectorizes: YF!s1=s \$\endgroup\$ – Luis Mendo Sep 23 '16 at 20:18
  • \$\begingroup\$ @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) \$\endgroup\$ – DJMcMayhem Sep 23 '16 at 20:20
  • \$\begingroup\$ Go ahead. I'll port that to Jelly to practice :-) \$\endgroup\$ – Luis Mendo Sep 23 '16 at 20:22
5
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Correction: port of Luis Mendo's: DJMcMayhem's MATL answer. :P \$\endgroup\$ – DJMcMayhem Sep 23 '16 at 20:26
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Dennis Sep 23 '16 at 21:43
  • 1
    \$\begingroup\$ @Dennis Thanks! I've used the first suggestion. The second one is too different, and is your approach \$\endgroup\$ – Luis Mendo Sep 23 '16 at 21:54
5
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

Retina, 31 bytes

Byte count assumes ISO 8859-1 encoding. Convert input to unary, generate the range from 1 to n, each on its own line. Match the primes.

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

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

\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ You can get to 7 bytes %þ`¬Sċ2 using a table of remainders. \$\endgroup\$ – miles Sep 23 '16 at 22:53
  • 1
    \$\begingroup\$ ḍþḅ1ċ2 saves a byte. \$\endgroup\$ – Dennis Sep 24 '16 at 19:05
4
\$\begingroup\$

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>

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

PowerShell v2+, 98 bytes

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

Caution: This is slow for large input.

Basically the unary-based lookup from Is this number a prime?, coupled with a for loop and a $j++ counter. A little additional logic on the front to account for edge cases input 1 and 2, due to how the fenceposting works in the for loops.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ ÅPg is what it'd be now, right? \$\endgroup\$ – Magic Octopus Urn Jan 18 '18 at 17:55
3
\$\begingroup\$

CJam, 7 bytes

rim!mF,

Try it online! Uses a factorization function.

Explanation:

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

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.
\$\endgroup\$
3
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ @tfbninja yes you right, but I gave the function part only, which does not compile by it's own \$\endgroup\$ – Ariel Bereslavsky Jan 16 '18 at 21:27
  • \$\begingroup\$ @tfbninja Actually, it's not. \$\endgroup\$ – Erik the Outgolfer Jan 17 '18 at 13:09
  • \$\begingroup\$ cool sounds good! \$\endgroup\$ – FantaC Jan 17 '18 at 15:41
2
\$\begingroup\$

Pyth - 7 6 bytes

Since others are using prime factorization functions...

l{sPMS

Test Suite.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Pyke, 8 6 bytes

SmPs}l

Try it here!

Thanks to Maltysen for new algorithm

SmP    -    map(factorise, input)
   s   -   sum(^)
    }  -  uniquify(^)
     l - len(^)
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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!

;╗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.
\$\endgroup\$
2
\$\begingroup\$

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)

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Why do you use isInt(...)?1:0 and not just isInt(...) \$\endgroup\$ – Roman Gräf Sep 25 '16 at 18:09
  • \$\begingroup\$ @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... \$\endgroup\$ – Mario Sep 25 '16 at 20:12
2
\$\begingroup\$

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)

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 2**n % n==2 is not enough as primaly test \$\endgroup\$ – RosLuP Jan 18 '18 at 16:42
  • \$\begingroup\$ @RosLuP That is why the base case of n==0 should add 1 (to account for the n=2 case). \$\endgroup\$ – Sandeep Silwal Jan 19 '18 at 0:02
  • \$\begingroup\$ 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 \$\endgroup\$ – RosLuP Jan 19 '18 at 7:48
  • \$\begingroup\$ For example 341=11*31 but ( 2^341) mod 341==2 \$\endgroup\$ – RosLuP Jan 19 '18 at 8:44
  • \$\begingroup\$ @RosLuP: Ah ok yes, I looked it up. These numbers are called Fermat Psuedoprimes but they appear to be quite rare :P \$\endgroup\$ – Sandeep Silwal Jan 19 '18 at 22:55
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 50+2 46+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)
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Neil Sep 24 '16 at 17:47
  • \$\begingroup\$ @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. \$\endgroup\$ – Hedi Sep 24 '16 at 19:11
1
\$\begingroup\$

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;
 }
\$\endgroup\$
  • \$\begingroup\$ 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,. \$\endgroup\$ – Kevin Cruijssen May 12 '17 at 14:27
1
\$\begingroup\$

q 35 bytes

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

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.