Exercism - Sieve of Eratosthenes

Preparation

Before we click on our next exercise, let’s see what concepts of DART we need to consider

So we need to use the following concepts.

Classes and Constructors

Classes define blueprints for objects. Constructors initialize instances with specific values and can perform initialization logic.

class Sieve {
  final int limit;
  late final List<int> primes;
  
  // Constructor - initializes limit and calculates primes
  Sieve(this.limit) {
    primes = _sieveWithBits();
  }
}

void main() {
  Sieve sieve = Sieve(10);
  print(sieve.primes); // [2, 3, 5, 7]
}

Late Initialization (`late final`)

The late keyword allows you to declare a variable that will be initialized later, but before it’s used. late final means it can only be assigned once, after the object is created.

class Sieve {
  final int limit;
  late final List<int> primes; // Will be initialized in constructor
  
  Sieve(this.limit) {
    primes = _sieveWithBits(); // Initialize here
  }
}

void main() {
  Sieve sieve = Sieve(10);
  // primes is now initialized and can be used
  print(sieve.primes); // [2, 3, 5, 7]
}

Uint8List (Bit Arrays)

Uint8List from dart:typed_data is a fixed-length list of 8-bit unsigned integers. It’s perfect for creating memory-efficient bit arrays where each bit represents a boolean value.

import 'dart:typed_data';

void main() {
  // Create a Uint8List with 2 bytes (16 bits)
  Uint8List bits = Uint8List(2);
  
  // Each byte can store 8 bits
  // bits[0] stores bits 0-7
  // bits[1] stores bits 8-15
  
  // Set bit 3 (in first byte)
  bits[0] |= (1 << 3);
  
  // Check if bit 3 is set
  bool isSet = (bits[0] & (1 << 3)) != 0;
  print(isSet); // true
}

Bitwise Right Shift (`>>`)

The right shift operator (>>) moves bits to the right, effectively dividing by a power of 2. It’s used to find which byte contains a specific bit.

void main() {
  // Right shift by 3 (divide by 8) to find byte index
  int bitIndex = 15;
  int byteIndex = bitIndex >> 3; // 15 / 8 = 1 (integer division)
  print(byteIndex); // 1
  
  // Bit 0-7 are in byte 0
  // Bit 8-15 are in byte 1
  // Bit 16-23 are in byte 2
  // etc.
  
  int bit = 5;
  int byte = bit >> 3; // 5 / 8 = 0
  print(byte); // 0 (bit 5 is in first byte)
}

Bitwise Left Shift (`<<`)

The left shift operator (<<) moves bits to the left, effectively multiplying by a power of 2. It’s used to create bit masks.

void main() {
  // Left shift to create bit mask
  int bitPosition = 3;
  int mask = 1 << bitPosition; // 1 * 2^3 = 8 (binary: 1000)
  print(mask); // 8
  
  // Use mask to set bit
  int value = 0;
  value |= (1 << 3); // Set bit 3
  print(value); // 8
  
  // Check if bit is set
  bool isSet = (value & (1 << 3)) != 0;
  print(isSet); // true
}

Bitwise AND (`&`)

The bitwise AND operator (&) compares each bit of two numbers. It returns 1 if both bits are 1, otherwise 0. It’s used to check if a specific bit is set.

void main() {
  int value = 9; // Binary: 1001
  
  // Check if bit 0 is set (value & 1)
  bool bit0 = (value & 1) != 0;
  print(bit0); // true (9 & 1 = 1)
  
  // Check if bit 1 is set (value & 2)
  bool bit1 = (value & 2) != 0;
  print(bit1); // false (9 & 2 = 0)
  
  // Check if bit 3 is set (value & 8)
  bool bit3 = (value & 8) != 0;
  print(bit3); // true (9 & 8 = 8)
  
  // General: check if bit n is set
  int n = 3;
  bool isSet = (value & (1 << n)) != 0;
  print(isSet); // true
}

Bitwise OR (`|`)

The bitwise OR operator (|) compares each bit of two numbers. It returns 1 if either bit is 1. It’s used to set bits.

void main() {
  int value = 0; // Binary: 0000
  
  // Set bit 0
  value |= (1 << 0); // value = 1 (binary: 0001)
  
  // Set bit 2
  value |= (1 << 2); // value = 5 (binary: 0101)
  
  // Set bit 3
  value |= (1 << 3); // value = 13 (binary: 1101)
  
  print(value); // 13
}

Bit Manipulation Helper Functions

Helper functions make bit manipulation more readable. They abstract the bitwise operations needed to set and get bits in a bit array.

import 'dart:typed_data';

void main() {
  Uint8List bits = Uint8List(2);
  
  // Helper to set a bit
  void setBit(int n) {
    bits[n >> 3] |= (1 << (n & 7));
  }
  
  // Helper to get a bit
  bool getBit(int n) {
    return (bits[n >> 3] & (1 << (n & 7))) != 0;
  }
  
  // Use helpers
  setBit(5);
  print(getBit(5)); // true
  print(getBit(4)); // false
}

Bitwise AND with 7 (`& 7`)

The expression n & 7 is equivalent to n % 8. It extracts the bit position within a byte (0-7). This is more efficient than modulo for powers of 2.

void main() {
  // n & 7 finds the bit position within a byte (0-7)
  int n = 15;
  int bitPos = n & 7; // 15 % 8 = 7
  print(bitPos); // 7
  
  // Examples
  print(0 & 7); // 0
  print(7 & 7); // 7
  print(8 & 7); // 0 (8 is in next byte)
  print(15 & 7); // 7
  print(16 & 7); // 0 (16 is in next byte)
  
  // Used to find which bit within a byte
  // n >> 3 finds the byte
  // n & 7 finds the bit within that byte
}

List Comprehensions (Collection For)

List comprehensions provide a concise way to create lists by iterating and conditionally including elements. They’re perfect for collecting primes.

void main() {
  // List comprehension: collect primes
  List<int> primes = [
    for (var i = 2; i <= 10; i++)
      if (isPrime(i)) i
  ];
  print(primes); // [2, 3, 5, 7]
  
  // List comprehension: collect unmarked numbers
  List<bool> marked = [false, false, true, false, true, false];
  List<int> unmarked = [
    for (var i = 0; i < marked.length; i++)
      if (!marked[i]) i
  ];
  print(unmarked); // [0, 1, 3, 5]
}

For Loops with Step

For loops can increment by values other than 1 using compound assignment operators. This is essential for marking multiples in the sieve.

void main() {
  int prime = 3;
  int limit = 20;
  
  // Mark multiples of prime
  for (var j = prime * prime; j <= limit; j += prime) {
    print(j); // 9, 12, 15, 18
  }
  
  // Start from prime * prime (optimization)
  // Increment by prime each time
  // This marks all multiples: 9, 12, 15, 18, 21, ...
}

Square Root Optimization

The sieve only needs to check primes up to √limit. Any composite number larger than √limit will have been marked by a smaller prime factor.

void main() {
  int limit = 100;
  
  // Only check up to sqrt(limit)
  int sqrtLimit = (limit * limit).toInt(); // Approximation
  // Better: use i * i <= limit
  for (var i = 2; i * i <= limit; i++) {
    // Process prime i
    print(i); // 2, 3, 4, 5, 6, 7, 8, 9, 10
  }
  
  // Why this works:
  // If a number n > sqrt(limit) is composite,
  // it has a factor <= sqrt(limit) that already marked it
}

Integer Division (`~/`)

Integer division divides two numbers and returns an integer, discarding the remainder. It’s used to calculate the number of bytes needed for a bit array.

void main() {
  int limit = 100;
  
  // Calculate bytes needed (8 bits per byte)
  int bytes = ((limit + 1) ~/ 8) + 1;
  print(bytes); // (101 / 8) + 1 = 13 + 1 = 14
  
  // Add 1 to limit to include limit itself
  // Add 1 to bytes for safety (round up)
}

Introduction

You bought a big box of random computer parts at a garage sale. You’ve started putting the parts together to build custom computers.

You want to test the performance of different combinations of parts, and decide to create your own benchmarking program to see how your computers compare. You choose the famous “Sieve of Eratosthenes” algorithm, an ancient algorithm, but one that should push your computers to the limits.

Instructions

Your task is to create a program that implements the Sieve of Eratosthenes algorithm to find all prime numbers less than or equal to a given number.

A prime number is a number larger than 1 that is only divisible by 1 and itself. For example, 2, 3, 5, 7, 11, and 13 are prime numbers. By contrast, 6 is not a prime number as it not only divisible by 1 and itself, but also by 2 and 3.

The Algorithm

To use the Sieve of Eratosthenes, first, write out all the numbers from 2 up to and including your given number. Then, follow these steps:

Find the next unmarked number (skipping over marked numbers). This is a prime number.
Mark all the multiples of that prime number as not prime.
Repeat the steps until you’ve gone through every number. At the end, all the unmarked numbers are prime.

Note

The Sieve of Eratosthenes marks off multiples of each prime using addition (repeatedly adding the prime) or multiplication (directly computing its multiples), rather than checking each number for divisibility.

The tests don’t check that you’ve implemented the algorithm, only that you’ve come up with the correct primes.

Example

Let’s say you’re finding the primes less than or equal to 10.

Step 1: Write out 2, 3, 4, 5, 6, 7, 8, 9, 10, leaving them all unmarked.

2 3 4 5 6 7 8 9 10

Step 2: 2 is unmarked and is therefore a prime. Mark 4, 6, 8 and 10 as “not prime”.

2 3 [4] 5 [6] 7 [8] 9 [10]
↑

Step 3: 3 is unmarked and is therefore a prime. Mark 6 and 9 as not prime.

2 3 [4] 5 [6] 7 [8] [9] [10]
  ↑

Step 4: 4 is marked as “not prime”, so we skip over it.

2 3 [4] 5 [6] 7 [8] [9] [10]
     ↑

Step 5: 5 is unmarked and is therefore a prime. Mark 10 as not prime.

2 3 [4] 5 [6] 7 [8] [9] [10]
        ↑

Step 6: Continue through remaining numbers. 7 is unmarked and is therefore a prime.

Result: 2, 3, 5, and 7 are still unmarked, meaning they’re the primes less than or equal to 10.

How does the Sieve of Eratosthenes work?

The Sieve of Eratosthenes efficiently finds all primes up to a limit:

Create bit array: Use a bit array where each bit represents whether a number is prime (0 = prime, 1 = not prime)
Mark 0 and 1: These are not prime
Iterate from 2 to √limit: For each unmarked number i:
- i is prime
- Mark all multiples of i starting from i² (optimization: smaller multiples already marked)
Collect primes: All unmarked numbers from 2 to limit are primes

The key optimizations:

Start marking from i²: Multiples less than i² are already marked by smaller primes
Only check up to √limit: Any composite > √limit has a factor ≤ √limit that already marked it
Use bit arrays: Memory-efficient representation (1 bit per number instead of 1 byte)

For example, finding primes ≤ 10:

Start: all unmarked
i=2: mark 4, 6, 8, 10
i=3: mark 9 (6 already marked)
i=4: skip (already marked)
i=5: mark 10 (already marked)
Result: 2, 3, 5, 7 are prime

Solution

import 'dart:typed_data';

class Sieve {
  final int limit;
  late final List<int> primes;

  Sieve(this.limit) {
    primes = _sieveWithBits();
  }

  List<int> _sieveWithBits() {
    if (limit < 2) return [];

    // Use a bit array for memory efficiency
    final bytes = ((limit + 1) ~/ 8) + 1;
    final bits = Uint8List(bytes);

    // Helper functions to set/get bits
    void setBit(int n) => bits[n >> 3] |= (1 << (n & 7));
    bool getBit(int n) => (bits[n >> 3] & (1 << (n & 7))) != 0;

    // Mark 0 and 1 as not prime
    setBit(0);
    setBit(1);

    // Sieve algorithm
    for (var i = 2; i * i <= limit; i++) {
      if (!getBit(i)) {
        for (var j = i * i; j <= limit; j += i) {
          setBit(j);
        }
      }
    }

    // Collect primes
    return [
      for (var i = 2; i <= limit; i++)
        if (!getBit(i)) i
    ];
  }
}

Let’s break down the solution:

import 'dart:typed_data' - Import typed data:
- Imports Uint8List for efficient bit arrays
- Provides fixed-length lists of bytes
class Sieve - Main class:
- Encapsulates the sieve algorithm
- Stores limit and calculated primes
final int limit - Upper bound:
- Maximum number to check for primality
- All primes ≤ limit will be found
late final List<int> primes - Primes list:
- Will be initialized in constructor
- Contains all primes ≤ limit
- late final means initialized once in constructor
Sieve(this.limit) - Constructor:
- Initializes limit field
- Calculates primes immediately
- Primes are ready when object is created
List<int> _sieveWithBits() - Sieve implementation:
- Private method that implements the algorithm
- Uses bit array for memory efficiency
- Returns list of primes
if (limit < 2) return [] - Edge case:
- No primes less than 2
- Returns empty list immediately
final bytes = ((limit + 1) ~/ 8) + 1 - Calculate bytes needed:
- Each byte stores 8 bits
- (limit + 1) ~/ 8 calculates bytes needed
- + 1 adds extra byte for safety (round up)
- Example: limit=10 → (11 ~/ 8) + 1 = 1 + 1 = 2 bytes
final bits = Uint8List(bytes) - Create bit array:
- Fixed-length list of bytes
- Each bit represents a number’s primality
- Memory efficient: 1 bit per number
void setBit(int n) => bits[n >> 3] |= (1 << (n & 7)) - Set bit helper:
- n >> 3 finds which byte contains bit n (divide by 8)
- n & 7 finds which bit within the byte (0-7)
- 1 << (n & 7) creates bit mask
- |= sets the bit using OR
bool getBit(int n) => (bits[n >> 3] & (1 << (n & 7))) != 0 - Get bit helper:
- n >> 3 finds which byte
- n & 7 finds which bit
- 1 << (n & 7) creates bit mask
- & checks if bit is set
- Returns true if bit is set (number is marked/not prime)
setBit(0) and setBit(1) - Mark non-primes:
- 0 and 1 are not prime numbers
- Mark them immediately
for (var i = 2; i * i <= limit; i++) - Main sieve loop:
- Iterate from 2 to √limit (optimization)
- i * i <= limit is more efficient than i <= sqrt(limit)
- Only need to check up to √limit
if (!getBit(i)) - Check if prime:
- If bit is not set, i is prime
- If bit is set, i is composite (skip)
for (var j = i * i; j <= limit; j += i) - Mark multiples:
- Start from i² (optimization: smaller multiples already marked)
- Increment by i to mark all multiples
- Continue until limit
setBit(j) - Mark as composite:
- Sets the bit for number j
- Marks it as not prime
return [for (var i = 2; i <= limit; i++) if (!getBit(i)) i] - Collect primes:
- List comprehension iterates from 2 to limit
- Includes i only if bit is not set (i is prime)
- Returns list of all primes

The solution efficiently finds all primes using a bit array for memory efficiency and optimizations (starting from i², checking only up to √limit). The bit manipulation makes the code fast and memory-efficient for large limits.

A video tutorial for this exercise is coming soon! In the meantime, check out my YouTube channel for more Dart and Flutter tutorials. 😉

Visit My YouTube Channel