Добро пожаловать в первую публикацию категории «Давайте решим»!

Сегодня я объясню вам, что такое Решето Эратосфена на самом деле. Это простой и полезный алгоритм для программистов. Особенно для тех, кто интересуется соревновательным программированием.

Если вы еще этого не сделали, обязательно ознакомьтесь с серией LitCodes Competitive Programming. Реализация кода в сегодняшней публикации выполнена на C++.

Проверить:

Что такое Сито Эратосфена?

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

Идея

Вначале все числа в массиве (кроме 1) простые. Мы перебираем массив, если текущее число помечено как простое, все его кратные помечаются как не простые. Мы повторяем тот же процесс, пока не переберем весь массив чисел.

Пример 1

У нас есть массив с именем my_array, который содержит числа от 1 до 11.
Как я уже говорил, 1 не является простым числом, а все остальные элементы массива являются простыми.

Теперь давайте представим, что наше текущее число равно 2.
2 помечено как простое (истина), поэтому каждое число, кратное 2, будет помечено как не простое (ложь). В нашем массиве числа, кратные 2, равны 4, 6, 8 и 10.

Поэтому, когда мы находим числа, кратные нашему текущему числу (2), мы помечаем их как не простые (ложь).

Реализация кода

Идея кода:

  1. Здесь мы определяем наш массив с именем isPrime
  2. Мы определяем нашу функцию sieve_func, которая принимает число (n), где (n) — предел.
  3. Через первый цикл for мы устанавливаем каждое значение из 2 нашего массива isPrime в true (так как числа являются простыми)
  4. Во втором цикле for от 2 до n/2 проверяем, является ли текущее число простым.
  5. Внутри тела оператора if мы создаем еще один цикл for, который установит каждое кратное нашему текущему числу значение false.
  • Почему второй цикл равен n/2?

Потому что все числа, кратные текущему числу, будут больше (i/2). Если мы возьмем (n) в качестве верхней границы, наше (j) будет больше предела (j — каждое кратное). Мы не хотим, чтобы это произошло.

  • Как присвоить каждому множителю значение false?

Используя цикл for с (j), равным (i*2), мы присваиваем каждому числу в шагах (j+i) значение false. Это уловка, используемая для просмотра всех множественных чисел.

Код C++:

#include <iostream>
using namespace std;
const int Nmax = 100001;
bool isPrime[Nmax];
void sieve(int n){
    for(int i = 2; i<=n; i++){
        isPrime[i]=true;
    }
for(int i = 2; i<=n/2; i++){
        if(isPrime[i]){
            for(int j=i*2; j<=n; j+=i){
                isPrime[j] = false;
            }
        }
    }
}
int main(){
    sieve(100);
    for(int i = 1; i<=100; i++){
        if(isPrime[i]) cout<<i<<" ";
    }
    return 0;
}

Краткое содержание

В сегодняшней публикации мы рассмотрели алгоритм решета Эратосфена.

Я надеюсь, что это побудило вас начать свой путь в соревновательном программировании. Это всего лишь один из многих алгоритмов и задач, которые мы рассмотрим в серии «Решим LitCode».

👩🏻‍💻 Надеюсь, эта информация была полезной и мотивировала вас. Чтобы узнать больше, посетите мой официальный блог litcode.net и @thelitcode в Instagram.

Удачного творчества! — Ирма П.