Напишем на языке Си программу, проверяющую является ли число простым. Для проверки будем использовать простейший алгоритм, основанный непосредственно на определении простого числа.
Простое число — определение
Простое число — это натуральное число (то есть целое и положительное), большее, чем единица, которое делится без остатка только на единицу и само на себя.
Список простых чисел (приведем до ста) начинается так: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97…
Функция на Си, проверяющая — является ли число простым
Напишем на языке Си функцию, которая будет проверять — простое ли число. И возвращать результат проверки в виде логической величины bool: true (да) или false (нет).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// функция проверяет - простое ли число n bool isPrime(int n) { // если n > 1 if (n > 1) { // в цикле перебираем числа от 2 до n - 1 for (int i = 2; i < n; i++) if (n % i == 0) // если n делится без остатка на i - возвращаем false (число не простое) return false; // если программа дошла до данного оператора, то возвращаем true (число простое) - проверка пройдена return true; } else // иначе возвращаем false (число не простое) return false; } |
Алгоритм проверки числа n на простоту строится на определении термина простого числа.
Во-первых число n должно быть больше 1 (проверяем это в строке 5 с помощью условного оператора if), а во-вторых проверяемое число должно иметь только два делителя: 1 и n (проверяем это в строках 8-10 с помощью цикла for и оператора if).
Для работы данного метода требуется подключить заголовочный файл stdbool.h в начале файла с исходным кодом. В stdbool.h содержится определение логических констант true и false, поскольку в чистой версии языка Си они отсутствуют.
Для подключения используем директиву include:
|
1 |
#include <stdbool.h> |
Тестирование функции для проверки простоты числа
Для проверки работы функции напишем код программы в main:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int main() { // в данной переменной будем хранить число, которое необходимо проверить на простоту int n; // вывод текста в консоль printf("Input a number: "); // читаем число n scanf_s("%d", &n); // выводим информацию о том, простое ли число n: 1 - да, 0 - нет printf("Is prime: %d\n", isPrime(n)); } |
Также не забудем включить в программу необходимый заголовочный файл для работы функций ввода-вывода данных (scanf и printf):
|
1 |
#include <stdio.h> |
Запустим программу и убедимся, что алгоритм работает корректно.
Единица в выводе (Is prime: 1) означает, что число — простое. Ноль говорил бы об обратном.
Видеоурок по теме проверки числа на простоту на языке Си
Статьи по теме
Поиск простых чисел. Решето Эратосфена на Си
Поиск простых чисел. Решето Сундарама на Си
Тест Миллера – Рабина – проверка числа на простоту
Поделиться в соц. сетях: