Дано натуральное число N. Задача состоит в том, чтобы проверить, является ли число простым или нет.
Примеры:
Ввод: 5
Вывод:5 – этопростое число.
Объяснение.5 — простое число, потому что оно делится только на 1 и на себя.
Ввод: 4
Вывод:4 не является простым числом.
Простое число — это целое положительное число, кроме 1, которое делится на 1 и само на себя. Например: 2, 3, 5, 7, 11, 13, 17 — первые несколько простых чисел.
Примечание. 0 и 1 не являются ни простыми, ни составными.
Подход. Эффективный подход к решению этой проблемы состоит в том, чтобы перебирать все числа, начиная с 2 и заканчивая sqrt(N), используя цикл for и на каждой итерации проверять, полностью ли он делит N.
Если N полностью делится на него, N не является простым числом. В этом случае флаг устанавливается в 1, а цикл завершается с помощью оператора break.
Если мы не нашли никакого числа между 2 и sqrt(N), которое точно делит N, то это означает, что N простое число, тогда флаг не меняется на 1.
Наконец, проверьте, равен ли флаг 0, тогда N простое число, а если флаг установлен в 1, то N не является простым числом.
Обратите внимание, что мы инициализировали флаг как 0 во время запуска нашей программы.
Примечание. Мы запустили цикл от 2 до sqrt(N) вместо N/2, потому что один из множителей N должен быть меньше или равен квадратному корню из N.
Код:
// Программа на C, чтобы проверить,
// число простое или нет
#include ‹math.h›
#include ‹stdio.h›
основной ()
{
int n, i, флаг = 0;
printf("Введите число: ");
scanf("%d", &n);
// Итерация от 2 до sqrt(n)
для (я = 2; я ‹= sqrt (n); я ++) {
// Если n делится на любое число между
// 2 и квадратный корень из n, то это не так
// основной
if (n % i == 0) {
флаг = 1;
перерыв;
}
}
// Пограничные случаи
if (n == 0 || n == 1) {
printf("%d не является ни простым, ни составным", n);
}
еще {
// если флаг равен 0, то число простое
если (флаг == 0)
printf("%d — простое число", n);
// если флаг равен 1, то он не простой
еще
printf("%d не является простым числом", n);
}
вернуть 0;
}
Вывод:
Введите число: 5
5 это простое число
Временная сложность: O(N1/2)
Пространственная сложность: O(1)
