Студопедия — Решето Аткина.
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Решето Аткина.






Алгоритмы формирования таблиц простых чисел

 

Описание алгоритма:

Алгоритм состоит из следующих шагов.

1. Выписываются все натуральные числа из диапазона от 1 до n.

 

2. Перебираются все возможные пары чисел x, y, где x<=sqrt(n) и y<=sqrt(n). Т.е. (1,1), (1,2),…, (1,sqrt(n)), (2,1), (2,2),…, (sqrt(n),sqrt(n)).

3. Для каждой пары чисел вычисляются значения следующих трех уравнений:

a) 4*x^2+y^2;

b) 3*x^2+y^2;

c) 3*x^2-y^2, значение вычисляется только при x>y.

4. Для каждого вычисленного значения уравнений вычисляются остатки от деления на 12, причем

a) если остаток равен 1 или 5 для значения первого уравнения;

b) если остаток равен 7 для значения второго уравнения;

с) если остаток равен 11 для значения третьего уравнения.

То в исходном ряду чисел от 1 до n число помечается как простое.

Замечание: если какое-то число Z присутствует в значениях нескольких уравнений (допустим a и b), и остаток от деления на 12 этого числа удовлетворяет условиям обоих групп, то число помечается два раза: сначала как простое, а потом как составное.

5. На последнем этапе проверяется кратность помеченных чисел квадратам простых чисел из диапазона от 5 до sqrt(n). Если число кратно квадрату, то оно помечается как составное.

Пример работы алгоритма для n = 40.

1. Выписываем все натуральные числа из диапазона от 1 до 40.


2. Перебираются все возможные пары чисел от (1,1) до (6,6) (Т.к. sqrt(40) ~ 6).

2. Вычисляем значения уравнений для каждой пары чисел x и y.

 

 

 



4. Вычисляем остаток от деления на 12 и помечаем простые числа.



5. Проверяем кратность помеченных чисел квадратам простых из диапазона от 5 до 6.

5 — простое число, 6 — составное, значит проверяем на кратность 5^2=25 помеченные числа. В результате 25 — нужно вычеркнуть. В итоге остаются только простые числа от 1 до 40.

 

Алгоритм имеет асимптотическую сложность и требует бит памяти. На входных значениях порядка решето Аткина быстрее решета Эрастофена в 9.2 раза. Приведу график роста превосходства алгоритма Аткина на числах от 2 до :

В результате можно наблюдать следующую скорость выполнения:

10 000 000 0.15 сек.
100 000 000 2.16 сек.
1 000 000 000 48.76 сек.

 







Дата добавления: 2015-10-12; просмотров: 1667. Нарушение авторских прав; Мы поможем в написании вашей работы!



Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...

Эндоскопическая диагностика язвенной болезни желудка, гастрита, опухоли Хронический гастрит - понятие клинико-анатомическое, характеризующееся определенными патоморфологическими изменениями слизистой оболочки желудка - неспецифическим воспалительным процессом...

Признаки классификации безопасности Можно выделить следующие признаки классификации безопасности. 1. По признаку масштабности принято различать следующие относительно самостоятельные геополитические уровни и виды безопасности. 1.1. Международная безопасность (глобальная и...

Прием и регистрация больных Пути госпитализации больных в стационар могут быть различны. В цен­тральное приемное отделение больные могут быть доставлены: 1) машиной скорой медицинской помощи в случае возникновения остро­го или обострения хронического заболевания...

Схема рефлекторной дуги условного слюноотделительного рефлекса При неоднократном сочетании действия предупреждающего сигнала и безусловного пищевого раздражителя формируются...

Уравнение волны. Уравнение плоской гармонической волны. Волновое уравнение. Уравнение сферической волны Уравнением упругой волны называют функцию , которая определяет смещение любой частицы среды с координатами относительно своего положения равновесия в произвольный момент времени t...

Медицинская документация родильного дома Учетные формы родильного дома № 111/у Индивидуальная карта беременной и родильницы № 113/у Обменная карта родильного дома...

Studopedia.info - Студопедия - 2014-2024 год . (0.011 сек.) русская версия | украинская версия