Найти минимальное 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);
}

Объяснение кода листинга программы

  1. Включаем необходимые заголовочные файлы для работы с assert, printf и memcpy
  2. Определяем функцию factorize, которая принимает два аргумента: n и a. Факторизует число n, используя простой алгоритм перебора делителей от 2 до n-1 и сохраняет их в массив a. Проверяет, что n больше 1, иначе выдает ошибку. Возвращает размер массива a, т.е. количество найденных делителей.
  3. Определяем функцию exclude_factors, которая принимает массив a, его размер na, массив b и его размер nb. Удаляет из массива a все элементы, которые присутствуют в массиве b.
  4. В функции main задаем число n = 1234567. Создаем массив n_factors размером 1024 и вызываем функцию factorize для числа n, сохраняя результаты в массив n_factors. Проверяем, что количество найденных делителей больше 0. Берем первый делитель x = n_factors[0].
  5. Запускаем цикл, который будет перебирать все возможные значения x, начиная с n_factors[0], пока не найдем нужное нам x. В каждой итерации цикла создаем массив x_factors размером 1024 и вызываем функцию factorize для числа x, сохраняя результаты в массив x_factors. Используем функцию exclude_factors для удаления из массива n_factors всех элементов, которые есть в массиве x_factors. Если количество найденных делителей равно 0, то мы нашли нужное нам x и выходим из цикла. Увеличиваем значение x на 1 и продолжаем цикл.
  6. Выводим найденное значение x.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

5   голосов , оценка 4.4 из 5
Похожие ответы