Description
Find all primes up to n by iteratively marking multiples. Create a boolean array [2..n] initially true. For each p from 2 to √n: if p is still marked prime, mark all multiples of p (starting at p²) as composite. Remaining true indices are primes. Time O(n log log n).
Algorithm Flowchart
graph TD
A1["Upper limit n"]
B1["Create is_prime 2..n\nall true; p = 2"]
C1["Mark multiples of p\nj = p², j += p"]
D1{"p² ≤ n?"}
D2{"is_prime[p]?"}
D3{"j ≤ n?"}
E1["Mark is_prime j false\nj = j + p"]
E2["p = p + 1"]
F1["Return primes\nindices where true"]
A1 --> B1
B1 --> D1
D1 -->|No| F1
D1 -->|Yes| D2
D2 -->|No| E2
D2 -->|Yes| C1
C1 --> D3
D3 -->|Yes| E1
E1 --> D3
D3 -->|No| E2
E2 --> D1
classDef red fill:#ff6b6b,color:#fff,stroke:#c0392b
classDef yellow fill:#ffd43b,color:#000,stroke:#f59f00
classDef green fill:#51cf66,color:#fff,stroke:#40c057
classDef lightblue fill:#74c0fc,color:#fff,stroke:#4dabf7
classDef violet fill:#b197fc,color:#fff,stroke:#9775fa
classDef lavender fill:#e6e6fa,color:#333,stroke:#b19cd9
class A1 red
class B1 yellow
class C1 green
class E1,E2 lightblue
class F1 violet
class D1,D2,D3 lavender
Color Scheme (GLMP 6-Color)
Red
Triggers & Inputs
Triggers & Inputs
Yellow
Structures & Objects
Structures & Objects
Green
Processing & Operations
Processing & Operations
Light Blue
Intermediates & States
Intermediates & States
Violet
Products & Outputs
Products & Outputs
Lavender
Decision diamonds
Decision diamonds
Process Statistics
- Nodes: 10
- Edges: 14
- Decision nodes: 3
- Complexity: O(n log log n)
Keywords
- sieve of Eratosthenes
- prime numbers
- NIST DADS
- number theory