Найти минимальное x, такое что x! делится на n - C (СИ)
Формулировка задачи:
Дано: n.
Найти: минимальное x, такое что x! делится на n.
Решение задачи: «Найти минимальное x, такое что x! делится на n»
textual
Листинг программы
#include <assert.h> #include <stdio.h> #include <string.h> unsigned factorize(unsigned n, unsigned a[]) { assert(n > 1); unsigned *f = a; for (unsigned d = 2; d < n; ++d) for (; n % d == 0; n /= d) *f++ = d; if (n != 1) *f++ = n; assert(f > a); return f - a; } unsigned exclude_factors(unsigned a[], unsigned na, const unsigned b[], unsigned nb) { unsigned id = 0, ia = 0; for (unsigned ib = 0; ia < na && ib < nb; ) if (a[ia] < b[ib]) a[id++] = a[ia++]; else if (a[ia] > b[ib]) ++ib; else ++ia, ++ib; unsigned n = na - ia; if (n > 0) { memcpy(a + id, a + ia, n * sizeof *a); id += n; } return id; } int main(void) { unsigned n = 1234567; unsigned n_factors[1024]; unsigned nn = factorize(n, n_factors); assert(nn > 0); unsigned x = n_factors[0]; do { unsigned x_factors[1024]; unsigned nx = factorize(x, x_factors); nn = exclude_factors(n_factors, nn, x_factors, nx); if (nn == 0) break; ++x; } while (1); printf("%u\n", x); }
Объяснение кода листинга программы
- Включаем необходимые заголовочные файлы для работы с assert, printf и memcpy
- Определяем функцию factorize, которая принимает два аргумента: n и a. Факторизует число n, используя простой алгоритм перебора делителей от 2 до n-1 и сохраняет их в массив a. Проверяет, что n больше 1, иначе выдает ошибку. Возвращает размер массива a, т.е. количество найденных делителей.
- Определяем функцию exclude_factors, которая принимает массив a, его размер na, массив b и его размер nb. Удаляет из массива a все элементы, которые присутствуют в массиве b.
- В функции main задаем число n = 1234567. Создаем массив n_factors размером 1024 и вызываем функцию factorize для числа n, сохраняя результаты в массив n_factors. Проверяем, что количество найденных делителей больше 0. Берем первый делитель x = n_factors[0].
- Запускаем цикл, который будет перебирать все возможные значения x, начиная с n_factors[0], пока не найдем нужное нам x. В каждой итерации цикла создаем массив x_factors размером 1024 и вызываем функцию factorize для числа x, сохраняя результаты в массив x_factors. Используем функцию exclude_factors для удаления из массива n_factors всех элементов, которые есть в массиве x_factors. Если количество найденных делителей равно 0, то мы нашли нужное нам x и выходим из цикла. Увеличиваем значение x на 1 и продолжаем цикл.
- Выводим найденное значение x.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д