Спочатку дізнайтеся визначення
Просте число — це ціле число, більше за 1, з двома додатними дільниками: 1 і самим числом. Перші прості числа: 2, 3, 5, 7, 11 і 13. Число 1 не є ні простим, ні складеним, а 2 — єдине парне просте число.
Перевіряйте тільки до квадратного кореня
Щоб перевірити натуральне число n, вам не потрібно пробувати кожне число, менше n. Якщо n має множник, більший за квадратний корінь, він також повинен мати відповідний множник, менший за квадратний корінь. Тому достатньо перевірити можливі дільники до квадратного кореня.
- Якщо число менше 2, воно не є простим.
- Перевірте, чи ділиться воно на 2. Якщо воно парне і більше 2, воно не просте.
- Спробуйте непарні дільники від 3 до квадратного кореня. Якщо якесь ділиться порівну, число є складеним.
- Якщо жодне не ділиться порівну, число є простим.
Приклад: чи є 97 простим числом?
Квадратний корінь із 97 трохи менший за 10. Перевірте можливі прості дільники до цього моменту: 2, 3, 5 і 7. Число не ділиться ні на одне з них, тому 97 є простим.
Для 91 перевірка знаходить 7: 91 ÷ 7 = 13. Цього достатньо, щоб показати, що 91 є складеним; немає потреби перевіряти більші дільники.
Поширені помилки
- Виклик 1 простого. Просте число повинно мати рівно два додатних дільники, тоді як 1 має лише один.
- Припускаючи, що кожне непарне число є простим. Непарні складові, такі як 9, 15, 21 і 91, мають непарні дільники.
- Перевірка лише кількох малих дільників для великого числа. Перевірка має охоплювати всі можливі дільники до квадратного кореня або використовувати перевірений алгоритм простоти.
UsefulVerse перевіряє практичне введення цілих чисел локально у вашому браузері. Основним результатом є перевірка на подільність, а не доказ криптографічного ключа чи заміна спеціалізованого програмного забезпечення теорії чисел.