Ugrás a tartalomhoz

решето Эратосфена

A Wikiszótárból, a nyitott szótárból

Orosz

решето Эратосфена (rešeto Eratosfena)

Kiejtés

  • IPA: [rʲɪʂɨtə ɪrətəsfʲɪnə]

Főnév

решето Эратосфена • (rešeto Eratosfena)

  1. (informatika) Eratoszthenész szitája

Решето Эратосфена в математике и программировании (C++)

1. Что такое Решето Эратосфена?

📌 Решето Эратосфена – это быстрый алгоритм нахождения всех простых чисел от 2 до N.

🔹 Идея алгоритма:
1. Заполняем массив флагов (предполагаем, что все числа от 2 до N – простые).
2. Убираем все кратные числам, начиная с 2 (оставляем только простые).
3. Выводим оставшиеся числа – это и есть простые числа!

🔹 Скорость работы: O(n log log n) – намного быстрее, чем перебор всех чисел!


2. Как работает Решето Эратосфена?

🔹 Пример: найти простые числа до 30.
1. Записываем числа от 2 до 30:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

2. Первое простое число – 2. Убираем все его кратные (4, 6, 8, 10, ...).
2 3 X 5 X 7 X 9 X 11 X 13 X 15 X 17 X 19 X 21 X 23 X 25 X 27 X 29 X

3. Следующее простое – 3. Убираем все кратные (9, 15, 21, ...).

4. Переходим к 5, 7 и продолжаем…

5. Оставшиеся числа – простые!

✅ Ответ: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29


3. Реализация Решета Эратосфена в C++

#include <iostream>
#include <vector>
using namespace std;

// Функция Решето Эратосфена
void sieveOfEratosthenes(int n) {
    vector<bool> prime(n + 1, true); // Создаём массив флагов (true = простое)
    prime[0] = prime[1] = false; // 0 и 1 - не простые числа

    for (int i = 2; i * i <= n; i++) { // Перебираем числа от 2 до sqrt(n)
        if (prime[i]) { // Если число ещё не зачёркнуто
            for (int j = i * i; j <= n; j += i) {
                prime[j] = false; // Убираем все кратные i
            }
        }
    }

    // Вывод простых чисел
    cout << "Простые числа до " << n << ": ";
    for (int i = 2; i <= n; i++) {
        if (prime[i]) cout << i << " ";
    }
    cout << endl;
}

int main() {
    int limit;
    cout << "Введите предел: ";
    cin >> limit;

    sieveOfEratosthenes(limit);
    return 0;
}

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

Введите предел: 30
Простые числа до 30: 2 3 5 7 11 13 17 19 23 29

🔹 Как работает код?
- Создаём массив prime[], где true – это возможное простое число.
- Начинаем с 2, убираем все его кратные.
- Переходим к 3, 5, 7 и повторяем.
- Оставшиеся true – это простые числа!


4. Оптимизированная версия Решета Эратосфена

📌 Оптимизация:
✅ Начинаем удаление с i * i, а не i * 2 (все меньшие уже убраны).
✅ Перебираем только нечётные числа (экономит 2 раза больше памяти).

#include <iostream>
#include <vector>
using namespace std;

void optimizedSieve(int n) {
    if (n < 2) return;
    
    vector<bool> prime(n + 1, true);
    prime[0] = prime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= n; j += i) { // Убираем кратные
                prime[j] = false;
            }
        }
    }

    cout << "Простые числа: ";
    for (int i = 2; i <= n; i++) {
        if (prime[i]) cout << i << " ";
    }
    cout << endl;
}

int main() {
    int n;
    cout << "Введите число: ";
    cin >> n;
    
    optimizedSieve(n);
    return 0;
}

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

Введите число: 50
Простые числа: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

5. Скорость работы Решета Эратосфена

📌 Алгоритм работает за O(n log log n) – очень быстро даже для больших n!

🔹 Сравнение скорости работы:

Метод Время работы
Перебор (O(n√n)) Медленный
Решето (O(n log log n)) Быстрый
Улучшенное решето (O(n)) Очень быстрый


6. Применение Решета Эратосфена

✅ Криптография (RSA, ключи шифрования).
✅ Анализ больших данных (простые множители).
✅ Оптимизация алгоритмов (фильтрация чисел).
✅ Генерация случайных чисел (PRNG).


7. Вывод

🔹 Решето Эратосфена – один из самых быстрых алгоритмов нахождения простых чисел.
🔹 Работает за O(n log log n), что делает его эффективным даже для больших n!
🔹 Используется в криптографии, анализе данных, числовых вычислениях. 🚀

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=решето_Эратосфена&oldid=3488167”