Каталог@Mail.ru - каталог ресурсов интернет

Алгоритм получения простых чисел

1. Что нам нужно

Задача: составить алгоритм быстрого получения первых n > 1 простых чисел.

НУЖНЫЕ ПОНЯТИЯ ИЗ ЭТОЙ ОПЕРЫ ЕСТЬ ЗДЕСЬ.

2. Способ "в лоб"

Задаём функцию, которая определяет, является ли заданное число простым. После этого вызываем эту функцию для натуральных чисел, начиная с 2, пока не накопим n простых чисел.

Преимущество: быстро пишется на C++, Visual Basic и прочих языках высокого уровня и не требует мозгов.

Недостаток: слишком много операций. В данном случае при проверке очередного числа x на простоту не используется информация о том, какие числа от 2 до x-1 являются простыми, а какие составными. При этом, как было написано тута, нет смысл проверять остатки от деления x на составные числа, меньшие x. А ведь составных чисел большинство. Нетрудно догадаться, что доля простых чисел среди первых 10N, где N - натуральное, не может быть больше 40%.

3. Наш ответ Чемберлену

Основные положения нашего алгоритма таковы.

П1. Если число x не делится ни на одно из простых чисел, лежащих в диапазоне от 2 до , то x-простое число.
П2. Простые числа, большие 2, не могут быть чётными. Простые числа, большие 10, могут оканчиваться только на 1, 3, 7, 9, но не на 5.
П3. Самое маленькое простое число есть 2.

В итоге алгоритм таков.

Вход: n - сколько первых простых чисел нам нужно.

1. Число x=2 - простое. Заносим его в СПИСОК. Полагаем x = 3.

2. Проверяем по П1, зная СПИСОК, является ли x простым числом. Если является, заносим его в СПИСОК.
Если теперь получено n простых чисел, возвращаем СПИСОК. Иначе ещё не получено n простых чисел, переходим к шагу 3.

3. Увеличиваем x на 2, а если теперь x > 10 и x делится на 5, то увеличиваем x ещё на 2. Теперь переходим к шагу 2.

Важное замечание: использовать П1 можно и без квадратного корня: если y*y > x, то y не входит в диапазон от 2 до p. В исходнике, представленном ниже, используется только целочисленная арифметика.

4. Халявный исходник

Скачать исходник к описанному в пункте 3 алгоритму можно по этой ссылке.

Язык: C++. Цена: 10 спасибо, отправка СМС не нужна.

Производительность реализации: справляется за 3-5 сек. при n = 1 млн. на 4 гигах, 2,66 МГц.

copyright © Исканцев Н.В., 2012

К математическому разделу
На главную
X