Sieve of Eratosthenes

Definition

Definition

The Sieve of Eratosthenes is an efficient algorithm for finding all prime numbers up to a specified integer. It works by iteratively marking the multiples of each prime number starting from 2, which are not prime, until no more multiples can be found

Explanation

Begins by creating a list of consecutive integers starting from 2 up to a specified maximum value. It then repeatedly finds the smallest unmarked number in the list (which is a prime number) and marks all of its multiples as composite (not prime). This process continues until there are no more unmarked numbers left in the list. The remaining unmarked numbers are all prime

Guidance

• Create a list of consecutive integers from 2 to the maximum value
• Start with the first unmarked number (2) and mark all of its multiples as composite
• Find the next unmarked number (which is a prime), and repeat the process of marking its multiples as composite
• Continue this process until there are no more unmarked numbers left in the list
• The remaining unmarked numbers are all prime

Tips

• utilize a boolean array to efficiently mark numbers as prime or composite
• avoid checking even numbers greater than 2 since they are not prime
• optimize the algorithm by only iterating up to the square root of the maximum value to mark multiples

Practice

Practice

sieve_of_eratosthenes(maxValue):
  Let isPrime be an array of Boolean values, indexed from 0 to maxValue, initialized to true
  isPrime[0] = false
  isPrime[1] = false

  for i from 2 to square_root(maxValue):
    if isPrime[i] is true:
      for j from i^2 to maxValue with step i:
        isPrime[j] = false

  primes = empty list
  for i from 2 to maxValue:
    if isPrime[i] is true:
      append i to primes

  return primes

Solution

package main

func sieveOfEratosthenes(n int) []int {
    primes := make([]bool, n+1)
    var result []int

    for i := 2; i <= n; i++ {
        primes[i] = true
    }

    for p := 2; p*p <= n; p++ {
        if primes[p] == true {
            for i := p * p; i <= n; i += p {
                primes[i] = false
            }
        }
    }

    for p := 2; p <= n; p++ {
        if primes[p] {
            result = append(result, p)
        }
    }

    return result
}

import java.util.ArrayList;
import java.util.List;

public class SieveOfEratosthenes {

  public static List<Integer> sieveOfEratosthenes(int n) {
    boolean[] primes = new boolean[n + 1];
    List<Integer> result = new ArrayList<>();

    for (int i = 2; i <= n; i++) {
      primes[i] = true;
    }

    for (int p = 2; p * p <= n; p++) {
      if (primes[p]) {
        for (int i = p * p; i <= n; i += p) {
          primes[i] = false;
        }
      }
    }

    for (int p = 2; p <= n; p++) {
      if (primes[p]) {
        result.add(p);
      }
    }

    return result;
  }
}

function sieveOfEratosthenes(n) {
  const primes = new Array(n + 1).fill(true);
  const result = [];

  for (let p = 2; p * p <= n; p++) {
    if (primes[p]) {
      for (let i = p * p; i <= n; i += p) {
        primes[i] = false;
      }
    }
  }

  for (let p = 2; p <= n; p++) {
    if (primes[p]) {
      result.push(p);
    }
  }

  return result;
}

fun sieveOfEratosthenes(n: Int): List<Int> {
    val primes = BooleanArray(n + 1) { true }
    val result = mutableListOf<Int>()

    for (p in 2..n) {
        if (primes[p]) {
            for (i in p * p..n step p) {
                primes[i] = false
            }
        }
    }

    for (p in 2..n) {
        if (primes[p]) {
            result.add(p)
        }
    }

    return result
}

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    result = []

    for p in range(2, int(n**0.5) + 1):
        if primes[p]:
            for i in range(p * p, n + 1, p):
                primes[i] = False

    for p in range(2, n + 1):
        if primes[p]:
            result.append(p)

    return result

fn sieve_of_eratosthenes(n: usize) -> Vec<usize> {
    let mut primes = vec![true; n + 1];
    let mut result = Vec::new();

    for p in 2..=n {
        if primes[p] {
            for i in (p * p..=n).step_by(p) {
                primes[i] = false;
            }
        }
    }

    for p in 2..=n {
        if primes[p] {
            result.push(p);
        }
    }

    result
}

function sieveOfEratosthenes(n: number): number[] {
  const primes: boolean[] = new Array(n + 1).fill(true);
  const result: number[] = [];

  for (let p = 2; p * p <= n; p++) {
    if (primes[p]) {
      for (let i = p * p; i <= n; i += p) {
        primes[i] = false;
      }
    }
  }

  for (let p = 2; p <= n; p++) {
    if (primes[p]) {
      result.push(p);
    }
  }

  return result;
}