Алгоритм Эратосфена для нахождения простых чисел
Алгоритм Эратосфена – это один из древнейших и наиболее известных методов нахождения всех простых чисел до заданного предела ( n ). Главной идеей алгоритма является поочередное исключение составных чисел из групп потенциальных простых чисел.
Алгоритм работает следующим образом:
- Создаем список чисел от 2 до ( n ). Изначально все числа в списке считаются простыми.
- Начинаем с первого простого числа ( p = 2 ). Оставляем это число как простое и исключаем все его кратные (начиная с ( p2 )) из списка, так как они не могут быть простыми.
- Находим следующее число в списке, которое не было исключено. Оно будет простым.
- Повторяем шаги 2 и 3, пока значение ( p2 \leq n ).
В результате в списке остаются только простые числа до ( n ).
Пример: найти все простые числа до 30.
- Начинаем с числа 2; оставляем его и удаляем все кратные ему числа: 4, 6, 8, 10, ...
- Следующее число 3: оставляем и удаляем кратные: 9, 12, 15, ...
- Далее 5 и 7 также остаются, так как все их кратные уже исключены ранее.
Таким образом, метод является эффективным для малых и средних диапазонов чисел благодаря своей простоте и малой вычислительной сложности.
Категория: Математика
Теги: числовые алгоритмы, простые числа, вычислительная математика