Решето Эратосфена: эффективный поиск простых чисел

Почему этот алгоритм важен?

Решето Эратосфена позволяет оценить:

• 🧮 Фундаментальные принципы работы с простыми числами
• ⚡ Эффективность оптимизированных алгоритмов
• 💾 Компромиссы между памятью и вычислениями
• 📊 Асимптотическую сложность и её практическое значение

Постановка задачи

Формулировка:

Найти все простые числа в диапазоне от 2 до N.

Примеры:

// Первый пример
Input: n = 10
Output: [2, 3, 5, 7] // Все простые числа от 2 до 10

// Второй пример
Input: n = 20
Output: [2, 3, 5, 7, 11, 13, 17, 19] // Все простые числа от 2 до 20

Принцип работы алгоритма

Решето Эратосфена основано на простом наблюдении:

Если p — простое число, то все числа вида k×p, где k > 1, являются составными.

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

1. Создаём список чисел от 2 до N
2. Начинаем с первого простого числа p = 2
3. Отмечаем все числа, кратные p, как составные
4. Находим следующее неотмеченное число — оно простое
5. Повторяем шаги 3-4 до тех пор, пока p² ≤ N

Подходы к решению

Решение 1: Классическое решето Эратосфена

function sieveOfEratosthenes(n) {
  // Создаём массив, где все элементы изначально помечены как простые
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false; // 0 и 1 не являются простыми
  
  // Проходим по всем числам до sqrt(n)
  for (let p = 2; p * p <= n; p++) {
    // Если число p простое, отмечаем его кратные как составные
    if (isPrime[p]) {
      for (let i = p * p; i <= n; i += p) {
        isPrime[i] = false;
      }
    }
  }
  
  // Собираем все простые числа в массив
  const primes = [];
  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) {
      primes.push(i);
    }
  }
  
  return primes;
}

Анализ решения:

✅ Простая реализация, соответствующая математическому описанию

✅ Эффективная временная сложность O(N log log N)

✅ Оптимизация: начинаем отмечать кратные с p² вместо 2p

❌ Требует O(N) дополнительной памяти

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Решение 2: Оптимизация по памяти 💾

function segmentedSieve(n) {
  const limit = Math.floor(Math.sqrt(n));
  const primes = sieveOfEratosthenes(limit); // Найдём простые числа до sqrt(n)
  const result = [...primes]; // Копируем начальные простые числа
  
  // Обрабатываем сегменты размером sqrt(n)
  const segmentSize = limit;
  
  for (let low = limit + 1; low <= n; low += segmentSize) {
    // Определяем границы текущего сегмента
    const high = Math.min(low + segmentSize - 1, n);
    
    // Локальное решето для текущего сегмента
    const segment = new Array(high - low + 1).fill(true);
    
    // Отмечаем составные числа в текущем сегменте
    for (const prime of primes) {
      // Находим первое кратное простого числа в текущем сегменте
      let firstMultiple = Math.ceil(low / prime) * prime;
      if (firstMultiple < low) {
        firstMultiple += prime;
      }
      
      // Отмечаем все кратные как составные
      for (let j = firstMultiple; j <= high; j += prime) {
        segment[j - low] = false;
      }
    }
    
    // Собираем простые числа из текущего сегмента
    for (let i = 0; i < segment.length; i++) {
      if (segment[i]) {
        result.push(low + i);
      }
    }
  }
  
  return result;
}

Особенности:

✅ Эффективно работает с большими диапазонами

✅ Значительно снижает требования к памяти O(√N)

✅ Хорошо работает с кешем процессора благодаря локальности данных

❌ Более сложная реализация

Решение 3: Битовая оптимизация 🔢

function bitSieve(n) {
  // Используем битовый массив вместо булевого
  // Каждый бит представляет нечётное число: 3, 5, 7, ...
  const size = Math.floor((n - 1) / 2);
  const sieve = new Uint8Array(Math.ceil(size / 8));
  
  function setBit(k) {
    const bit = k % 8;
    const byte = Math.floor(k / 8);
    sieve[byte] |= (1 << bit);
  }
  
  function getBit(k) {
    const bit = k % 8;
    const byte = Math.floor(k / 8);
    return (sieve[byte] & (1 << bit)) !== 0;
  }
  
  // 2 — единственное чётное простое число
  const primes = [2];
  
  // Итерируемся только по нечётным числам
  for (let p = 3; p <= n; p += 2) {
    const index = Math.floor((p - 3) / 2);
    
    if (!getBit(index)) {
      primes.push(p);
      
      // Отмечаем кратные как составные
      if (p * p <= n) {
        for (let i = p * p; i <= n; i += 2 * p) {
          const markIndex = Math.floor((i - 3) / 2);
          setBit(markIndex);
        }
      }
    }
  }
  
  return primes;
}

Характеристики:

✅ Использует в 8 раз меньше памяти по сравнению с булевым массивом

✅ Обрабатывает только нечётные числа, что сокращает вдвое количество операций

✅ Эффективно для очень больших диапазонов

❌ Сложнее для понимания и отладки

Сравнение производительности

Расширенные применения

Модификация для нахождения простых делителей

function primeFactors(n) {
  const primes = sieveOfEratosthenes(Math.floor(Math.sqrt(n)));
  const factors = [];
  
  for (const prime of primes) {
    while (n % prime === 0) {
      factors.push(prime);
      n /= prime;
    }
  }
  
  if (n > 1) {
    factors.push(n); // Если осталось простое число больше sqrt(n)
  }
  
  return factors;
}

Нахождение простых чисел в заданном диапазоне [L, R]

function primesInRange(l, r) {
  // Находим простые числа до sqrt(r)
  const limit = Math.floor(Math.sqrt(r));
  const smallPrimes = sieveOfEratosthenes(limit);
  
  // Создаём решето для диапазона [L, R]
  const size = r - l + 1;
  const isPrime = new Array(size).fill(true);
  
  // Отмечаем составные числа
  for (const prime of smallPrimes) {
    // Находим первое кратное prime в диапазоне [L, R]
    const start = Math.ceil(l / prime) * prime;
    
    for (let i = Math.max(start, prime * prime); i <= r; i += prime) {
      isPrime[i - l] = false;
    }
  }
  
  // Особые случаи для 0 и 1
  if (l <= 1 && r >= 1) {
    isPrime[1 - l] = false;
  }
  if (l <= 0 && r >= 0) {
    isPrime[0 - l] = false;
  }
  
  // Формируем результат
  const primes = [];
  for (let i = 0; i < size; i++) {
    if (isPrime[i]) {
      primes.push(l + i);
    }
  }
  
  return primes;
}

Практические применения 🌟

1. Криптография:

   • Генерация больших простых чисел для RSA
   • Создание криптографических ключей

2. Теория чисел:

   • Проверка гипотез о распределении простых чисел
   • Исследование свойств специальных простых чисел

3. Алгоритмы факторизации:

   • Основа для более сложных алгоритмов факторизации
   • Полезно при факторизации малых чисел

4. Олимпиадное программирование:

   • Решение задач, связанных с простыми числами
   • Оптимизация скорости работы программ

Оптимизации и рекомендации 💡

1. Для диапазонов < 10⁷:

   • Используйте классическое решето с битовой оптимизацией
   • Проверяйте только нечётные числа (кроме 2)

2. Для диапазонов > 10⁷:

   • Применяйте сегментированное решето
   • Ограничьте максимальный размер сегмента для оптимальной работы с кешем

3. Дополнительные оптимизации:

   • Проверяйте только простые числа до √N
   • Пропускайте кратные 2 и 3, используя колёсную факторизацию

Типичные ошибки

1. 🤦‍♂️ Неправильная обработка границ диапазонов
2. 😅 Переполнение памяти при работе с большими числами
3. 🔄 Избыточная проверка чисел, которые уже отмечены как составные
4. 🧮 Отсутствие оптимизации начального шага (p * p вместо 2 * p)

Эффективная реализация

function optimizedSieve(n) {
  if (n < 2) return [];
  if (n === 2) return [2];
  
  // Работаем только с нечётными числами, экономя половину памяти
  const size = Math.floor(n / 2);
  const sieve = new Uint8Array(Math.ceil(size / 8));
  
  // Функции для работы с битовым массивом
  const setBit = (k) => {
    sieve[k >>> 3] |= 1 << (k & 7);
  };
  
  const getBit = (k) => {
    return (sieve[k >>> 3] & (1 << (k & 7))) !== 0;
  };
  
  const sqrtN = Math.sqrt(n) | 0;
  
  for (let i = 1; i <= (sqrtN >>> 1); i++) {
    if (!getBit(i)) {
      // 2*i + 1 — текущее простое число
      const p = 2 * i + 1;
      
      // Отмечаем все нечётные кратные p
      for (let j = i + p; j < size; j += p) {
        setBit(j);
      }
    }
  }
  
  // Формируем список простых чисел
  const primes = [2]; // 2 — единственное чётное простое число
  
  for (let i = 1; i < size; i++) {
    if (!getBit(i)) {
      primes.push(2 * i + 1);
    }
  }
  
  return primes;
}

Заключение

Решето Эратосфена представляет собой:

• 🧮 Один из древнейших и наиболее эффективных алгоритмов в истории математики
• ⚡ Яркий пример того, как простая идея может привести к оптимальному решению
• 💾 Демонстрацию компромисса между временем работы и использованием памяти
• 🌟 Фундаментальный алгоритм с широким спектром современных применений

Несмотря на свой возраст (более 2000 лет), решето Эратосфена остаётся непревзойдённым по простоте и эффективности алгоритмом для нахождения всех простых чисел в заданном диапазоне, подтверждая ценность классических алгоритмов в современной компьютерной науке.