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

51 Answers 51

1
2
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\$
1
  • \$\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\$ Commented May 12, 2017 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\$
1
\$\begingroup\$

PARI/GP, 15 bytes

n->#factor(n!)~

Take the factorial and count its unique prime factors.

\$\endgroup\$
1
\$\begingroup\$

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

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
\$\endgroup\$
1
  • \$\begingroup\$ If (require math) is required for your program to work, you need to include it in your byte count. \$\endgroup\$
    – Pavel
    Commented May 11, 2017 at 15:41
1
\$\begingroup\$

Perl 6, 31 bytes

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

Try it online!

\$\endgroup\$
1
\$\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\$
5
  • \$\begingroup\$ 2**n % n==2 is not enough as primaly test \$\endgroup\$
    – user58988
    Commented Jan 18, 2018 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\$ Commented Jan 19, 2018 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\$
    – user58988
    Commented Jan 19, 2018 at 7:48
  • 1
    \$\begingroup\$ For example 341=11*31 but ( 2^341) mod 341==2 \$\endgroup\$
    – user58988
    Commented Jan 19, 2018 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\$ Commented Jan 19, 2018 at 22:55
1
\$\begingroup\$

(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".

\$\endgroup\$
1
\$\begingroup\$

Pyt, 3 bytes

řṗƩ

Explanation:

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

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ So one can use isprime right? \$\endgroup\$
    – user58988
    Commented Jan 18, 2018 at 16:45
1
\$\begingroup\$

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

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 )

\$\endgroup\$
1
\$\begingroup\$

Add++, 17 bytes

L,RB*f0b]@bLA1=!*

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Haskell, 46 42 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Apr 7, 2021 at 20:13
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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

Japt, 6 bytes

Êk â Ê

Try it

Êk â Ê     :Implicit input of integer
Ê          :Factorial
 k         :Prime factors
   â       :Deduplicate
     Ê     :Length
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Thunno 2 L, 2 bytes

Try it online!

Port of Dennis's 05AB1E answer.

Explanation

wƑ  # Implicit input
w   # Factorial of input
 Ƒ  # Unique prime factors
    # Implicit output of length
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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