Решето Эратосфена / Sieve of Eratosthenes

Решето Эратосфена — это алгоритм для нахождения всех простых чисел до заданного целого числа n. Этот метод назван в честь древнегреческого математика Эратосфена Киренского, который первым предложил его.

Основная идея

Алгоритм работает следующим образом:

1. Создается массив nums размером n+1, где каждый элемент изначально равен false (означает, что число не отмечено как составное).
2. Начиная с первого простого числа (2), алгоритм проходит по всем числам до n.
3. Для каждого простого числа i (которое не было отмечено как составное), алгоритм отмечает все его кратные как составные.
4. Процесс повторяется до тех пор, пока не будут проверены все числа до n.

Пример работы

Рассмотрим пример для n = 30:

1. Создаем массив nums размером 31 (от 0 до 30).
2. Начинаем с числа 2. Отмечаем все его кратные (4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30).
3. Переходим к следующему числу, которое не было отмечено, это 3. Отмечаем все его кратные (6, 9, 12, 15, 18, 21, 24, 27, 30).
4. Продолжаем этот процесс для чисел 5, 7, 11, 13, 17, 19, 23, 29.
5. В результате, все числа, которые остались неотмеченными, являются простыми.

Временная сложность

• O(n log log n): Процесс отметки составных чисел для каждого простого числа i требует n/i операций. Суммарное количество операций для всех простых чисел до n составляет n/2 + n/3 + n/5 + ..., что асимптотически равно n log log n.

Пространственная сложность

• O(n): Используется массив nums размером n+1 для отметки составных чисел.

Пример кода на Go

package main

import (
	"fmt"
)

// Функция sieveOfEratosthenes реализует алгоритм "Решето Эратосфена"
// для нахождения всех простых чисел до заданного целого числа n.
func sieveOfEratosthenes(n int) []bool {
	// Создаем массив nums размером n+1, где каждый элемент изначально равен false.
	// false означает, что число не отмечено как составное.
	nums := make([]bool, n+1)

	// Начинаем с первого простого числа (2) и проходим по всем числам до n.
	for i := 2; i <= n; i++ {
		// Если число i не отмечено как составное, то оно простое.
		if !nums[i] {
			// Отмечаем все кратные числа i как составные.
			// Начинаем с i*i, так как все предыдущие кратные уже были отмечены.
			for j := i * i; j <= n; j += i {
				nums[j] = true
			}
		}
	}

	// Возвращаем массив nums, где false означает простое число.
	return nums
}

func main() {
	// Задаем значение n, до которого будем искать простые числа.
	n := 30

	// Вызываем функцию sieveOfEratosthenes для нахождения простых чисел до n.
	nums := sieveOfEratosthenes(n)

	// Выводим все простые числа до n.
	fmt.Printf("Простые числа до %d:\n", n)
	for i := 2; i <= n; i++ {
		// Если число i не отмечено как составное, то оно простое.
		if !nums[i] {
			fmt.Printf("%d ", i)
		}
	}
}