Практический пример на 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

100 классических примеров на C

Другие расширения