Як швидко перевірити число на простоту?
Братимемо по черзі натуральні числа , починаючи з двійки, і перевіряти їх на простоту. Перевірка на простоту полягає в наступному: перебираючи числа з діапазону від до , ділитимемо на з залишком. Якщо при якомусь виявиться нульовий залишок, значить, ділиться на ціле, і число складова.
Просте число – це натуральне число більше 1, у якого є всього два дільники: одиниця і саме число. Наприклад: 11, 13, 17, 19 – список простих чисел.
- 9, 10, 12, 14 – приклади зі списку складених чисел.
- 9 – ділиться на 1, на 3 та на 9.
- 10 – ділиться на 1, на 2, на 5 та на 10.
- 12 – ділиться на 1, на 2, 3, 4, 6 та на 12.
30-Dec-2020
Якщо потрібно перевірити на простоту число типу int, то можна обійтися без двійкового множення.Асимптотика рішення
- перевірка на простоту
- тест Ферма
- алгоритм
- програмування
- спортивне
- асимптотика
- НІД
- двійкове множення