Упражнения по C/C++ для начинающих

Проверка числа на простоту в C и C++

В этом уроке вы проверите, является ли целое число простым, перебирая делители до его квадратного корня.

  • Начальный
  • Чтение: 2 мин
  • Примеров для запуска: 2

Введение

Какую задачу это решает

Простые числа используются в криптографии, хешировании и многих головоломках. Можно проверить простоту, перебрав все меньшие числа, но это пустая трата времени. Немного математики резко сокращает работу.

Пример из жизни

Проверка на простоту похожа на проверку, можно ли разрезать шоколадку из 29 долек на равные ряды. Вы пробуете ряды по 2, 3, 4 и 5. Когда размер ряда превысил квадратный корень, дальше проверять не нужно: такое разбиение уже нашлось бы раньше, ведь число рядов в нём меньше корня.

От шоколадки к коду
number > 1🍫 1 долька или меньше - не та шоколадка, что мы проверяем
divisor * divisor <= number📐 Пробовать размеры рядов только до квадратного корня
number % divisor == 0✂️ Делится ровно?
"29 is prime"✅ Деления не нашлось
Пробуйте делители до квадратного корня; останавливайтесь на первом.
Одним предложением

Простое число - это целое число больше 1, у которого ровно два делителя: 1 и оно само. Чтобы проверить число на простоту, перебирают делители от 2 до квадратного корня.

Главное

  1. Сначала prime равно number > 1, поэтому 0 и 1 не считаются простыми.
  2. Цикл выполняется, пока divisor * divisor <= number, так не нужно вычислять квадратный корень.
  3. Если number % divisor == 0, делитель найден: prime получает значение 0, и цикл завершается.
  4. Для 29 не подходит ни один делитель от 2 до 5, поэтому выводится "29 is prime".

Когда это нужно

  • Практика циклов с досрочным выходом.
  • Числовые головоломки и задачи по программированию.
  • Понимание того, почему проверка до квадратного корня ускоряет работу.

Когда это не нужно

  • Проверка многих чисел сразу: решето Эратосфена гораздо быстрее.
  • Очень большие числа в криптографии: используйте вероятностные тесты из библиотеки.

Примеры кода на C и C++

C
Запустить →
main.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
C++
Запустить →
main.cpp
#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 использует небольшие процедурные функции и открыто показывает, как данные представлены в памяти.

C++

C++ по-прежнему позволяет работать на низком уровне, но добавляет библиотечные типы и более безопасные абстракции.

Упражнения для практики

Запустите обе версии, а затем измените код, чтобы увидеть разницу в безопасности, которую даёт каждый язык.

  • Проверьте неверный ввод и граничные значения.
  • Скомпилируйте с флагами -Wall -Wextra -Wpedantic, чтобы включить больше предупреждений.
  • Вынесите общие объявления в заголовочный файл, а реализацию в отдельный файл.

Частые ошибки

1 считается простым

У 1 только один делитель, поэтому оно не простое.

Ошибка
int prime = 1;
Исправление
int prime = number > 1;

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи