Проверка числа на простоту в C и C++
В этом уроке вы проверите, является ли целое число простым, перебирая делители до его квадратного корня.
Введение
Какую задачу это решает
Простые числа используются в криптографии, хешировании и многих головоломках. Можно проверить простоту, перебрав все меньшие числа, но это пустая трата времени. Немного математики резко сокращает работу.
Пример из жизни
Проверка на простоту похожа на проверку, можно ли разрезать шоколадку из 29 долек на равные ряды. Вы пробуете ряды по 2, 3, 4 и 5. Когда размер ряда превысил квадратный корень, дальше проверять не нужно: такое разбиение уже нашлось бы раньше, ведь число рядов в нём меньше корня.
number > 1🍫 1 долька или меньше - не та шоколадка, что мы проверяемdivisor * divisor <= number📐 Пробовать размеры рядов только до квадратного корняnumber % divisor == 0✂️ Делится ровно?"29 is prime"✅ Деления не нашлосьПростое число - это целое число больше 1, у которого ровно два делителя: 1 и оно само. Чтобы проверить число на простоту, перебирают делители от 2 до квадратного корня.
Главное
- Сначала
primeравноnumber > 1, поэтому 0 и 1 не считаются простыми. - Цикл выполняется, пока
divisor * divisor <= number, так не нужно вычислять квадратный корень. - Если
number % divisor == 0, делитель найден:primeполучает значение 0, и цикл завершается. - Для 29 не подходит ни один делитель от 2 до 5, поэтому выводится
"29 is prime".
Когда это нужно
- Практика циклов с досрочным выходом.
- Числовые головоломки и задачи по программированию.
- Понимание того, почему проверка до квадратного корня ускоряет работу.
Когда это не нужно
- Проверка многих чисел сразу: решето Эратосфена гораздо быстрее.
- Очень большие числа в криптографии: используйте вероятностные тесты из библиотеки.
Примеры кода на C и C++
#include <stdio.h>
int main(void) {
int number = 29, prime = number > 1;
// A composite number has a factor no larger than its square root.
for (int divisor = 2; divisor * divisor <= number; ++divisor)
if (number % divisor == 0) { prime = 0; break; }
printf("%d is %sprime\n", number, prime ? "" : "not ");
}
29 is prime
#include <iostream>
int main() {
int number = 29;
bool prime = number > 1;
// Stop after the square root and on the first divisor.
for (int divisor = 2; divisor * divisor <= number && prime; ++divisor)
prime = number % divisor != 0;
std::cout << number << " is " << (prime ? "" : "not ") << "prime\n";
}
29 is prime
Сравнение C и C++
Цикл продолжается, только пока divisor * divisor <= number: если у числа есть делитель больше квадратного корня, он образует пару с меньшим делителем, который уже проверен. Найдя делитель, версия на C выходит из цикла через break, а версия на C++ останавливается благодаря условию && prime. Результат показывает, что 29 простое.
C использует небольшие процедурные функции и открыто показывает, как данные представлены в памяти.
C++ по-прежнему позволяет работать на низком уровне, но добавляет библиотечные типы и более безопасные абстракции.
Упражнения для практики
Запустите обе версии, а затем измените код, чтобы увидеть разницу в безопасности, которую даёт каждый язык.
- Проверьте неверный ввод и граничные значения.
- Скомпилируйте с флагами -Wall -Wextra -Wpedantic, чтобы включить больше предупреждений.
- Вынесите общие объявления в заголовочный файл, а реализацию в отдельный файл.
Частые ошибки
1 считается простым
У 1 только один делитель, поэтому оно не простое.
int prime = 1;
int prime = number > 1;
Закончили этот урок?
Отметьте его как изученный, чтобы следить за прогрессом.
Попрактикуйтесь на задаче
Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.
- Проверка на простое число Определите, является ли число простым. Легко
- List Primes With a Sieve Find primes up to a limit by marking composite multiples. Средне