НОУ ІНТУЇТ | лекція | Решето Ератосфена для знаходження простих чисел

1. Паралельний алгоритм пошуку простих чисел на основі решета Ератосфена
2. Опис 1-ої стадії
3. Опис 2-ої стадії

Анотація: У цій лекції розглянута теорія та реалізація алгоритму Ератосфена при знаходження простих чисел в контексті паралельного програмування.

Розглянемо задачу відшукання всіх простих чисел в інтервалі від 2 до деякого заданого числа . Виділимо в вихідному списку перше число, яке буде простим, і потім закреслимо як саме число 2, так і всі числа в списку, кратні йому. Щоб закреслити ці кратні числа, досить закреслити кожне друге число в списку, починаючи з числа 2. Потім Вибрано перше незачеркнутое число в якості чергового простого - їм буде число 3, і проводимо аналогічну процедуру, закреслюючи кожне третє число, починаючи з числа 3. Продовжуємо цю процедуру до тих пір, поки не дійдемо до чергового простого числа , Такого що . Легко бачити, що все залишилися незачеркнутимі числа в інтервалі є простими. Описаний метод знаходження простих чисел носить назву решета Ератосфена.

У цьому розділі буде описаний паралельний варіант алгоритму решета Ератосфена ( http://software.intel.com/en-us/articles/parallel-reduce/ ), Взятий із прикладів до бібліотеки Intel Threading Building Blocks ( http://www.threadingbuildingblocks.org/ ), І реалізований з використанням засобів бібліотеки PFX.

Паралельний алгоритм пошуку простих чисел на основі решета Ератосфена

Будемо розглядати задачу знаходження кількості простих чисел в інтервалі від 2 до ( ). (Насправді, в програмі буде матися спеціальний ключ, завдання якого буде приводити також до роздруківці всіх знайдених простих чисел).

Ідея алгоритму полягає в розбитті пошуку на 2 етапи: на 1-му етапі, який виконується послідовно, знаходяться всі прості числа в діапазоні за допомогою класичного методу решета Ератосфена. Знайдені прості числа, на 2-му етапі, дозволяють викреслити всі складові числа в діапазоні . Параллелизация полягає в тому, що діапазон розбивається на піддіапазони розміру , де , В яких пошук простих чисел може відбуватися незалежно.

У наведеному нижче алгоритмі враховуються також наступні властивості завдання:

1. оскільки всі парні числа, за винятком числа 2, є складовими, то в кожному піддіапазоні розміру розглядаються тільки непарні числа; наслідком цього є те, що розмір відповідних масивів дорівнює ;
2. в силу вибору розміру діапазону рівним , Кількість піддіапазонів, що розглядаються на 2-му етапі, також не перевищуватиме , Що, одночасно, є верхньою межею максимального числа потоків для обробки.

Опис 1-ої стадії

Призначення першої стадії? відшукати всі прості числа в піддіапазоні , Які потім будуть використовуватися для знаходження простих чисел в наступних піддіапазонах.

На початку 1-ої стадії, розміщуються масиви is_composite і prime_steps розмірності , Де перший масив служить для процедури просіювання, а в другому масиві зберігаються знайдений на цій стадії прості числа. У масиві is- composite елемент з номером відповідає непарному числу . Сам алгоритм полягає в звичайному просеивании Ератосфена, починаючи з елемента масиву is_composite з номером , Тобто, простого числа 3 (просте число 2 враховується спеціальним чином).

Опис 2-ої стадії

Друга стадія алгоритму полягає в одночасній обробці поддиапазонов, що укладаються в інтервалі , За допомогою декількох потоків.

Кожен потік, в загальному випадку, обробляє кілька піддіапазонів, зберігаючи кількість знайдених в них простих чисел у відповідному елементі масиву count_primes. Після закінчення роботи всіх потоків (тобто, після виходу з циклу Parallel .For), знаходиться сума всіх елементів масиву count_primes, яка додається до кількості знайдених простих чисел на першому етапі. Це значення - totalCountPrimes і стає результатом розв'язання задачі.

Ключовим моментом 2-ий стадії є обробка потоком одного піддіапазону, який починається з числа start, і має розмір . Для початку безпосереднього просіювання в цьому піддіапазоні, необхідно для кожного простого числа , Знайденого на першій стадії, обчислити зсув від початку даного піддіапазону? тобто, позицію, починаючи з якої буде відбуватися закреслення чисел з певним кроком, рівним .

Обчислення даного зсуву змістовно можна розбити на 4 етапи:

1. визначаємо число, на якому "зупинився" процес закреслення в попередньому поддиапазоне для даного ; це число визначається за формулою
2. так як всі піддіапазони, в тому числі і попередній, мають розмір , То від початку цього піддіапазону число відстоїть на відстані

3. оскільки в кожному піддіапазоні перевіряються на простоту тільки непарні числа, то позиція (відраховується від початку попереднього поддиапазона) наступного непарного числа (тобто, числа з якого почнеться просіювання в поточному поддиапазоне) визначається як

   якщо парне,

   і , якщо непарній

4. нарешті, визначаємо позицію щодо даного піддіапазону отриманого на попередньому кроці непарного числа, враховуючи, що в піддіапазоні розглядаються тільки непарні числа:

Розглянемо приклад обчислення зсуву відповідно до кроками, представленими вище.

нехай , тоді , І простими числами, знайденими в першому піддіапазоні, є 3,5,7.

Розглянемо, припустимо, третій за рахунком поддиапазон, що задається, відповідно параметрами і . тоді

Тобто, останнє число, кратне 3, в попередньому поддиапазоне є число 18, яке відстоїть від початку попереднього поддиапазона на відстані

Оскільки парне, то позиція наступного непарного числа визначається як

(Легко помітити, що ця позиція відповідає числу 21). Тоді, число 21, с якого ми почнемо закреслення чисел в третьому піддіапазоні з кроком 3, має зміщення відносно початку цього діапазону

Дійсно, число 21 є першим непарним числом в 3-му піддіапазоні, а тому воно має зсув 0 від початку цього піддіапазону.