Алгоритми → Пошук простих чисел
Так як я люблю вирішувати різні математичні задачки (projecteuler.net. Diofant.ru.), Постійно необхідно робити одні і ті ж дії. Тому я створив блог «Алгоритми», в якому буду періодично писати функції для вирішення різних завдань. Думаю, багатьом буде корисно.
Бажаючі також можуть поділитися своїми напрацюваннями. Посилання на інші ресурси кидати не потрібно, хто захоче, сам знайде через пошукові системи. Я любитель С ++, тому весь синтаксис буде на ньому.
Просте число - це число, яке ділиться без залишку тільки на одиницю і саме на себе.
Перша функція перевіряє, просте чи число. Для цього потрібно викликати функцію, передавши в неї число, яке нам потрібно перевірити на простоту.
Друга функція знаходить наступне просте число після числа, яке ми передаємо в аргументах функції.
Важливо! В обох функціях ми перевіряємо на залишок при діленні потрібного нам числа від двійки (так як на одиницю воно і так буде ділитися без залишку) до кореня нашого числа. Це важлива оптимізація нашого коду, яка дозволяє працювати нам з великими числами. Без неї пошук значення може значно сповільнитися.
а якщо в машинні коди переписати алгоритм? ) І було б цікаво виміряти, наскільки збільшиться продуктивність.
а якщо в машинні коди переписати алгоритм? ) Поламається переносимість і кроссплатформенность коду.
Ну це ж не ява. Я як раз і говорив про те, що б написати код під конкретний процесор щоб домогтися максимально можливої продуктивності. Алгоритм простий можна і під різні системи команд переписати, не убуде.
За продуктивність напишу в завтрашній статті :)
Спасибі, корисну справу робите.
Впринципі можна ще вести список простих чисел і подільність перевіряти по ним. Бо якщо число не ділиться ні на одне просте число, то воно так само є простим.
Це особливо прискорить алгоритм при великих числах тому будуть пропускатися всі великі масиви чисел
Знаю це властивість :)
Ну поки незнаю як реалізувати коротко і ясно. У майбутньому, сподіваюся, виправлю це
Ну наприклад завести список, в який записувати всі знайдені прості числа. А умова циклу замінити на:
Синтаксис правда більше на C # схожий, але суть начебто передає. List це список, і залишилося тільки вставити додавання чергового простого числа. Це вже за смаком або перед return або вже при використанні функцій
Поекспериментуйте, подивимося наскільки це себе виправдовує :)
З мого досвіду, є 2 практично однакових за швидкістю способу знаходження перших декількох мільйонів простих чисел:
1. решето Ератосфена,
2. перевірка подільності непарних чисел на вже знайдені прості числа (величиною до квадратного кореня з тестованого числа).
Наскільки я розумію суть цих методів однакова, тільки підхід з різних сторін. І тому виходить що решето Ератосфена має споживати набагато більше пам'яті тому вимагає попереднього масиву всіх чисел менше максимального шуканого.
Тобто для того що б знайти все прості числа до 1 000 000 нам необхідний масив з 999 999 чисел від 2 до 1 000 000, а в разі подільності чисел масив складатиметься тільки з простих чисел
Або є якась реалізація решета не жерло пам'ять?
Для решета можна використовувати бітовий масив. Працювати буде повільніше, але не знаю, наскільки повільніше.
1. В решеті робиться наголос на велику кількість простих операцій (додавань),
2. У другому способі упор на невелику кількість повільних операцій (ділення із залишком).
в сенсі вважати 1 в бите показником простого числа, а 0 немає, а потім за номером біта в масиві визначати число?
Чесно кажучи, з бітовими масивами не працював і наскільки складно реалізувати це буде не уявляю, але ідея передачі цієї решітки у вигляді картинки (bitmap) досить цікава))
Запис одиниці в i -й біт масиву a. що складається з 32-бітових чисел:
Читання не складніше. До речі, можна за раз перевіряти 32 числа на простоту, порівнюючи відповідному полі масиву a з 0xffffffff.
Було б набагато цікавіше перевести алгоритм в двійкову алгебру. Тоді можна максимально оптимізувати всі операції. Сучасні процесори мають розширені математичні команди, які можна було б використовувати в обхід універсальних компіляторів. Я коли давно робив щось подібне для системи команд x86. Але реалізувати подібне на системі команд intel64 було б набагато цікавіше.