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 Sep 23 '16 at 20:09
• what about prime factorization functions? Sep 23 '16 at 20:13
• Welcome to Programming Puzzles and Code Golf! Sep 23 '16 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. Sep 23 '16 at 20:44
• I think this is what @TheBikingViking meant to link to: Related Sep 23 '16 at 20:52

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. May 11 '17 at 15:41

Perl 6, 31 bytes

{+grep {$_%%none 2..^$_},2..$_}  Try it online! 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  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 Jan 18 '18 at 16:42 • @RosLuP That is why the base case of n==0 should add 1 (to account for the n=2 case). Jan 19 '18 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 Jan 19 '18 at 7:48 • For example 341=11*31 but ( 2^341) mod 341==2 – user58988 Jan 19 '18 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 Jan 19 '18 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 Jan 18 '18 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! 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! 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 sequence of x characters whose length represents the number. The resultant match is its return value in unary.

        # 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 bytes ((?=(?=(\3?))(\2?+x*?(?!(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, to make up for the lack of nested backreferences
(
\2?+           # Start from the previous value of \3 (as copied into \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 \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  Regex (.NET), 35 bytes ((?=((?>\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.

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. Apr 7 at 20:13