Codacoda
Back to Academy

math misc

Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a given limit. It works by iteratively marking the multiples of each prime starting from 2. The algorithm is highly efficient with O(n log log n) time complexity.

Use Cases

  • •Generating prime numbers for cryptographic key generation
  • •Solving number theory problems in competitive programming
  • •Precomputing prime factorizations for batch queries

Complexity Analysis

MetricBestAverageWorst
TimeO(n log log n)O(n log log n)O(n log log n)
SpaceO(n)

Visualization

Numbers 1 to 30123456789101112131415161718192021222324252627282930
Range: 1 — 30
Speed:1x
Sieve of Eratosthenes: Find all primes up to 30Step 1 / 9

Implementation

Output

Click "Run Code" to see output...