Prime Counting by the Sieve of Eratosthenes

Count primes at most n exactly with the sieve of Eratosthenes, excluding zero and one and limiting n to 1,000,000.

Description

The prime-counting function π(n) counts primes up to and including n.

The prime-counting function π(n) counts primes up to and including n. The sieve of Eratosthenes marks composite multiples instead of testing every integer independently.^[1]

The tool returns count. The indexing and output conventions below determine how to read these values.

When to use Prime Counting by the Sieve of Eratosthenes

Use this for the following task: Count primes at most n exactly with the sieve of Eratosthenes, excluding zero and one and limiting n to 1,000,000. Use the input and output conventions below to reproduce the intended mathematical quantity.

How to use Prime Counting by the Sieve of Eratosthenes and understand its results

Choose the required indexes, integers or sequence entries. Preserve decimal-string encodings where the field table specifies strings.
Enter n according to the field table, then run the tool.
Read count. Use the stated units, indexing and interpretation of the numerical result.
Keep exact decimal strings for subsequent integer arithmetic; distinguish them from any explicitly approximate numeric result.

Input field	Meaning	Value type and bounds	Requirement
n	Inclusive prime-counting limit (resource limit 1000000)	integer; minimum 0; maximum 1000000	Required

Create prime flags through the bounded inclusive limit, mark composite multiples and count remaining flags from two upward.

π(n)=Σ[p=2..n] indicator(prime(p))

The symbols and boundary conditions refer to the supplied fields and the implementation described above.

Output field	Meaning	Value type
count	Number of primes at most n	integer

json

{
  "input": {
    "n": 100
  },
  "output": {
    "count": 25
  }
}

Limitations and assumptions

Zero and one are excluded. The limit is at most one million, and the result is a count rather than a returned prime list.

Use the declared integer bounds and string formats. Large exact outputs remain decimal strings; numerical approximations use ordinary floating-point arithmetic. A rejected input is different from a valid zero count or false membership flag.

Alternative or Complementary methods

Choose Twin Prime Counting Function when you need its operation: Count twin-prime pairs whose smaller prime is at most n, testing the upper member even when it exceeds n; the sieve limit is capped at 1,000,000. Choose Goldbach Partition Count for the complementary operation: Count unordered prime pairs p≤q with p+q equal to an even n≥4, including equal-prime pairs, using a sieve limited to n≤1,000,000.

Background reference: Digital Library of Mathematical Functions, §27.2.

References

Digital Library of Mathematical Functions, §27.2 — National Institute of Standards and Technology

Similar or alternative tools

Twin Prime Counting Function
Count twin-prime pairs whose smaller prime is at most n, testing the upper member even when it exceeds n; the sieve limit is capped at 1,000,000.
Goldbach Partition Count
Count unordered prime pairs p≤q with p+q equal to an even n≥4, including equal-prime pairs, using a sieve limited to n≤1,000,000.