Практический пример на C 33 - Определение простого числа
100 классических примеров на C
Заголовок:Определить, является ли число простым.
Анализ программы:Простые числа, также называемые простыми, бесконечны по количеству. Натуральное число больше 1, которое не делится ни на одно другое натуральное число, кроме 1 и самого себя.
Исходный код программы:
Пример
#include<stdio.h>
#include<math.h>
#define MAX 1000 // Максимальный размер массива
int prime[MAX]; // Массив для хранения того, является ли число простым
// Простейший метод определения, является ли число простым (перебор)
int isPrimeNaive(int n)
{
if (n <= 1) // Числа, меньшие или равные 1, не являются простыми
return 0;
for (int i = 2; i < n; i++) // Проверять по очереди от 2 до n-1, делят ли они n
if (n % i == 0) // Если делится нацело, то число не простое
return 0;
return 1; // Если делитель не найден, то число простое
}
// Оптимизированная проверка простоты: проверять только до sqrt(n) и пропускать чётные числа
int isPrime(int n)
{
if (n <= 1) // Числа, меньшие или равные 1, не являются простыми
return 0;
if (n == 2) // 2 — простое число
return 1;
if (n % 2 == 0) // Исключить чётные числа
return 0;
int limit = (int)sqrt((double)n); // Достаточно проверять только до sqrt(n)
for (int i = 3; i <= limit; i += 2) // Начать с 3 и проверять только нечётные числа
{
if (n % i == 0) // Если делится нацело, то число не простое
return 0;
}
return 1; // Все проверки пройдены, n — простое число
}
// Инициализация решета: создание таблицы простых чисел
void sieve()
{
for (int i = 0; i < MAX; i++)
prime[i] = 1; // Считаем, что все числа простые
prime[0] = prime[1] = 0; // 0 и 1 не являются простыми
int limit = (int)sqrt((double)MAX); // Достаточно проверять до sqrt(MAX)
for (int i = 2; i <= limit; i++) // Начинаем с 2 и перебираем все числа
{
if (prime[i]) // Если i простое
{
for (int j = i * i; j < MAX; j += i) // Помечаем кратные i как не простые
prime[j] = 0;
}
}
}
// Определяем, является ли число простым, с помощью решета
int isPrimeSieve(int n)
{
return prime[n]; // Сразу возвращаем, является ли этот индекс простым
}
int main()
{
sieve(); // Инициализируем решето простых чисел
// Проверка различных чисел на простоту
printf("N=%d %d\n", 1, isPrime(1)); // Вывод: 1 не является простым
printf("N=%d %d\n", 2, isPrime(2)); // Вывод: 2 является простым
printf("N=%d %d\n", 3, isPrime(3)); // Вывод: 3 является простым
printf("N=%d %d\n", 4, isPrime(4)); // Вывод: 4 не является простым
printf("N=%d %d\n", 7, isPrime(7)); // Вывод: 7 является простым
printf("N=%d %d\n", 9, isPrime(9)); // Вывод: 9 не является простым
printf("N=%d %d\n", 13, isPrime(13)); // Вывод: 13 является простым
printf("N=%d %d\n", 17, isPrime(17)); // Вывод: 17 является простым
printf("N=%d %d\n", 100, isPrime(100)); // Вывод: 100 не является простым
printf("N=%d %d\n", 23, isPrime(23)); // Вывод: 23 является простым числом
printf("N=%d %d\n", 1, isPrime(1)); // Вывод: 1 не является простым
return 0;
}
Результат вывода приведённого выше примера (последняя цифра 1 означает простое число, 0 означает, что число не является простым):
N=1 0 N=2 1 N=3 1 N=4 0 N=7 1 N=9 0 N=13 1 N=17 1 N=100 0 N=23 1 N=1 0Другие расширения