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

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

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

Розглянемо задачу відшукання всіх простих чисел в інтервалі від 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 до   (   ) ( ). (Насправді, в програмі буде матися спеціальний ключ, завдання якого буде приводити також до роздруківці всіх знайдених простих чисел).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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