Mathematical AlgorithmsBeginner

Sieve of Eratosthenes

Find all prime numbers up to n by iteratively marking composites. Named after Eratosthenes of Cyrene (c. 276-194 BC).

#mathematical#prime-numbers#number-theory#ancient-algorithm

Complexity Analysis

Time (Average)

O(n log log n)

Expected case performance

Space

O(n)

Memory requirements

Time (Best)

O(n log log n)

Best case performance

Time (Worst)

O(n log log n)

Worst case performance

Find primes up to N (10-200)

Example Ranges:

How it works

• Find all prime numbers up to n
• Iteratively mark composites
• O(n log log n) time complexity
• O(n) space complexity
• Named after Eratosthenes of Cyrene (c. 276-194 BC)

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

Swaps

Array Accesses

Steps

1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default

Comparing

Swapped

Sorted

Code Execution

Currently executing

Previously executed

Implementation

Related Algorithms

View all in Mathematical Algorithms

Pascal's Triangle

Beginner

Triangular array of binomial coefficients where each number is the sum of the two numbers directly above it. Named after Blaise Pascal (1623-1662), though known to mathematicians centuries earlier. Demonstrates beautiful mathematical patterns including binomial expansion, combinatorics, and connections to Fibonacci numbers.

O(n²)

mathematicalcombinatorics

Start Learning

Euclidean Algorithm (GCD)

Beginner

Ancient algorithm from around 300 BC that efficiently computes the greatest common divisor of two integers. Based on the principle that GCD(a, b) = GCD(b, a mod b). One of the oldest algorithms in continuous use, forming the foundation of number theory, cryptography, and fraction simplification.

O(log min(a, b))

O(1)

mathematicalnumber-theory

Start Learning

Extended Euclidean Algorithm

Intermediate

Extends the Euclidean algorithm to find integers x and y satisfying Bézout's identity: ax + by = GCD(a, b). Not only computes GCD but also finds the coefficients of linear combinations. Fundamental to modular arithmetic, RSA cryptography, and solving linear Diophantine equations.

O(log min(a, b))

O(1)

mathematicalnumber-theory

Start Learning

Back to Mathematical Algorithms