Форум программистов, компьютерный форум, киберфорум
Наши страницы

C для начинающих

Войти
Регистрация
Восстановить пароль
 
emilgaziev
0 / 0 / 0
Регистрация: 25.01.2018
Сообщений: 3
#1

Найти минимальное x, такое что x! делится на n - C (СИ)

09.02.2018, 17:58. Просмотров 210. Ответов 12
Метки нет (Все метки)

Дано: n.
Найти: минимальное x, такое что x! делится на n.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.02.2018, 17:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти минимальное x, такое что x! делится на n (C (СИ)):

Дано натуральное число n. Получить все такие натуральные q, что n делится на q2 и не делится на q3 - C (СИ)
Дано натуральное число n. Получить все такие натуральные q, что n делится на q2 и не делится на q3

Найти такое число в двоичной записи которого содержится минимальное число нулей - C (СИ)
Среди простых чисел, не превосходящих заданного N, найти такое, в двоичной записи которого содержится минимальное число нулей. Вот я...

Найти такое число в двоичной записи которого содержится минимальное число нулей - C (СИ)
Среди простых чисел, не превосходящих заданного N, найти такое, в двоичной записи которого содержится минимальное число нулей.

Найти количество таких чисел из диапазона от 1 до N, что их сумма цифр делится на K - C (СИ)
Вводятся два числа N и K. Выведите количество чисел из диапазона от 1 до N таких, что их сумма цифр делится на K. мой код...

Найти числа, что образуют четырехзначное число, которое делится на их произведение - C (СИ)
Два двузначных числа, записанных одно за другим образуют четырехзначное число, которое делится на их произведение. Найти эти числа. Не...

Минимальное число больше 1000,которое нацело делится на 15 - C (СИ)
найти минимальное число больше 1000,которое нацело делится на 15. на си пост/пред условеие

12
Hitoku
Модератор
1344 / 940 / 477
Регистрация: 28.10.2016
Сообщений: 2,972
Завершенные тесты: 3
09.02.2018, 18:35 #2
C
1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
    int n, x = 1;
    long fact = 1;
    scanf("%i", &n);
    while (fact % n != 0) {
        x++;
        fact *= x;
    }
    printf("Number: %i\nFactorial: %i", x, fact);
    getch();
    return 0;
}
0
emilgaziev
0 / 0 / 0
Регистрация: 25.01.2018
Сообщений: 3
09.02.2018, 18:50  [ТС] #3
Я пока, что-то сделал. Но оно не совсем работает... Программа находит максимальный простой делитель и сколько раз он употребляется в числе.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
int main()
{
        int n, d, b, f, i=2, y=0;
        scanf("%d",&n);
        d=n;
        if (n==1)
        {
            printf ("%d", 0);
        }
        else
        {
        while(n!=1)
        {
            f=0;
            while(n%i==0)
            {
                f=1;
                n/=i;
            }
            i++;
        } 
        i--;
        while (d%i==0)
        {
            d/=i;
            b++;
        }
        while (b>0)
        {
        y=y+i;
        b--;
        }
        printf ("%d", y);
    }
        return 0;
}
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4013 / 2236 / 557
Регистрация: 18.10.2014
Сообщений: 3,858
10.02.2018, 06:39 #4
Цитата Сообщение от emilgaziev Посмотреть сообщение
Найти: минимальное x, такое что x! делится на n.
Неоптимальненько как-то, но тем не менее:

1. Факторизуем число n любым удобным нам способом
2. Начиная с минимального фактора k, факторизуем числа k, k+1, k+2 и т.д. Все получаемые факторы вычеркиваем из исходной факторизации n
3. То число k+i, на котором исходная факторизация станет пустой - это и есть наше искомое число x

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#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 час 42 минуты
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Неоптимальненько как-то, но тем не менее:
Действительно неоптимальненько. Намного лучший алгоритм

1. Факторизуем число n любым удобным нам способом
2. В нашей факторизации: каждую группу из k одинаковых факторов со значением f заменяем на минимальное число v, такое что в факторизации числа v! содержится не менее k факторов со значением f. Эта задача внешне похожа на исходную, но легко решается с помощью формулы Лежандра (также http://info.sernam.ru/book_eld.php?id=3)
3. Выбираем максимальное число в наборе, полученном на шаге 2 - это наше x

Например: n = 1440 = 25 * 32 * 5
Заменяем 25 на 8
Заменяем 32 на 6
Получаем { 8, 6, 5 }
Максимум: x = 8

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <assert.h>
#include <stdio.h>
#include <string.h>
 
typedef struct Factor 
{
  unsigned f, n;
} Factor;
 
unsigned factorize(unsigned v, Factor factors[])
{
  assert(v > 1);    
 
  Factor *factor = factors;
    
  for (unsigned d = 2; d < v; ++d)
  {
    unsigned n = 0;
    for (; v % d == 0; v /= d, ++n);
    if (n > 0)
      *factor++ = (Factor) { d, n };
  }
    
  if (v != 1)
    *factor++ = (Factor) { v, 1 };
 
  assert(factor > factors);
  return factor - factors;
}
 
unsigned count_factorial_factors(unsigned v, unsigned f)
{
  unsigned n = 0;
 
  for (unsigned p = f; p <= v; p *= f)
    n += v / p;
 
  return n;
}
 
void replace_factors(Factor factors[], unsigned n)
{
  for (unsigned i = 0; i < n; ++i)
  {
    assert(factors[i].n > 0);
    if (factors[i].n == 1)
      continue;
 
    unsigned v = factors[i].f * factors[i].n;
    assert(count_factorial_factors(v, factors[i].f) >= factors[i].n);
 
    while (count_factorial_factors(v - factors[i].f, factors[i].f) >= factors[i].n)
      v -= factors[i].f;
 
    factors[i] = (Factor) { v, 1 };
  }
}
 
unsigned max_f(const Factor factors[], unsigned n)
{
  unsigned max = 0;
 
  for (unsigned i = 0; i < n; ++i)
    if (factors[i].f > max)
      max = factors[i].f;
 
  return max;
}
 
int main(void)
{
  unsigned n = 1234567;
 
  Factor n_factors[1024];
  unsigned nn = factorize(n, n_factors);
  replace_factors(n_factors, nn);
  unsigned x = max_f(n_factors, nn);
 
  printf("%u\n", x);
}
Цикл по count_factorial_factors внутри replace_factors выглядит несколько некузяво: я "нащупываю" ответ через формулу Лежандра, вместо того, чтобы вычислять его впрямую. Но все равно это намного эффективнее предыдущего варианта.
0
Байт
Диссидент
Эксперт C
17217 / 11287 / 1789
Регистрация: 24.12.2010
Сообщений: 22,219
10.02.2018, 12:22 #5
Hitoku, интересно, как вы представляете работу своего кода при, скажем, n=37. В то время как ответ очевиден.

Добавлено через 17 минут
Я бы пошел таким путем. Пусть есть фактор pk (p - простое)
C
1
2
3
4
5
6
7
8
9
10
yp = p;
for(k--; k> 0; k--) {
  yp++;
  kk = k;
  while(kk%p==0) {
     k--;
     kk /= p;
  }
}
// yp - минимальное число, такое, что y! делится на p[SUP]k[/SUP]
Далее находим максимальное yp по всем факторам.

Добавлено через 7 минут
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
x = 1;
for(p=2; n >1; p++) {
 if (n%p==0) {
   k = 0;
   whiile(n%p==0) {
      k++;
      n / = p;
    }
 }
 yp = p;
 for(k--; k> 0; k--) {
   yp++;
   kk = k;
   while(kk%p==0) {
     k--;
     kk /= p;
   }
 }  
 if (yp > x) x = yp;
}
Вот такой получился псевдокод.
Не проверял. Но идея, надеюсь, понятна...
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4013 / 2236 / 557
Регистрация: 18.10.2014
Сообщений: 3,858
10.02.2018, 15:09 #6
Цитата Сообщение от Байт Посмотреть сообщение
Но идея, надеюсь, понятна...
Не понятно только, какое отношение предложенный цикл имеет к нахождению этого числа yp. В чем идея? В чем смысл деления показателя степени на основание степени?
0
Байт
Диссидент
Эксперт C
17217 / 11287 / 1789
Регистрация: 24.12.2010
Сообщений: 22,219
10.02.2018, 16:46 #7
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
В чем идея? В чем смысл деления показателя степени на основание степени?
Да, возможно я не точно выразил свою мысль, и соответственно, неправильно реализовал ее в коде.
А мысли были вот какие.
Вот есть 3k. Надо набрать k троек. 3! содержит 1 тройку. 6! - дает вторую. А 9! добавляет еще парочку.
Аналогично 5k 5!-9! одна пятерка. 10! + еще одна. По одной прибавляют 15! 20!. А вот 25 прибавляет сразу 2.
30, 35, 40, 45 - по одной пятерке. 50 - пару ... 125 - 3 пятерки.
Да, будет свободная минутка, попробую как-то оформить свою мысль. П посте 5 я ее оформил явно неправильно. Прошу прощения у почтенной публики.
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4013 / 2236 / 557
Регистрация: 18.10.2014
Сообщений: 3,858
10.02.2018, 16:58 #8
Цитата Сообщение от Байт Посмотреть сообщение
Вот есть 3k. Надо набрать k троек. 3! содержит 1 тройку. 6! - дает вторую. А 9! добавляет еще парочку.
Аналогично 5k 5!-9! одна пятерка. 10! + еще одна. По одной прибавляют 15! 20!. А вот 25 прибавляет сразу 2.
30, 35, 40, 45 - по одной пятерке. 50 - пару ... 125 - 3 пятерки.
Да, будет свободная минутка, попробую как-то оформить свою мысль.
Вы изначально пытаетесь в точности повторить алгоритм из моего ответа выше (см. вторую часть). А ваши рассуждения про делители - это попытка вывести формулу Лагранжа.

Формула Лагранжа дает нам количество делителей по известному факториалу. Нам же наоборот надо найти минимальный факториал по данному количеству делителей. Я не придумал ничего лучше, кроме как искать ответ в цикле, применяя формулу Лагранжа. Интересно было бы получить прямой способ вычисления ответа, если это возможно.
0
Байт
Диссидент
Эксперт C
17217 / 11287 / 1789
Регистрация: 24.12.2010
Сообщений: 22,219
10.02.2018, 17:12 #9
Может быть вот так (начиная со строчки 10.)
C
1
2
3
4
5
6
7
8
9
10
11
yp = 0;  // Число, факториал которого разделится на p^k
kx = 0;  // Сколько набралось сомножителей p
for(j = p; kx < k; j+=p) {
  yp += p;
  jj = j;
  while(jj%p == 0) {
     kx ++;
     jj /= p;
  }
}
if (yp > x) x = yp;
Добавлено через 2 минуты
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Вы изначально пытаетесь в точности повторить алгоритм из моего ответа выше
Вполне возможно. Надеюсь, большого греха в этом нет?
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4013 / 2236 / 557
Регистрация: 18.10.2014
Сообщений: 3,858
10.02.2018, 17:44 #10
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
это попытка вывести формулу Лагранжа.
Лежандра. Блин. Лежандра.
0
easybudda
Модератор
Эксперт CЭксперт С++
9913 / 5836 / 975
Регистрация: 25.07.2009
Сообщений: 11,005
11.02.2018, 01:40 #11
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
 
int main(void) {
    unsigned n;
    
    while ( printf("Number: ") && scanf("%u", &n) == 1 && n ) {
        unsigned i;
        
        for ( i = 1; i < n; ++i )
            if ( n % i == 0 && i * i > n )
                break;
        
        printf("%u! probably must be a multiple of %u\n", i, n);
    }
    
    return 0;
}
0
Байт
Диссидент
Эксперт C
17217 / 11287 / 1789
Регистрация: 24.12.2010
Сообщений: 22,219
11.02.2018, 12:03 #12
easybudda, Мне кажется, что для n=125 ваш код даст ответ 25. В то время как i = 15 уже подходит.
Или, скажем, n= 250...
Хотя придумывание примеров, опровергающих ваш код, - тоже интересная задача
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4013 / 2236 / 557
Регистрация: 18.10.2014
Сообщений: 3,858
12.02.2018, 03:58 #13
Цитата Сообщение от easybudda Посмотреть сообщение
C
1
2
3
4
        
        for ( i = 1; i < n; ++i )
            if ( n % i == 0 && i * i > n )
                break;
В таком виде - врет на всех квадратах, начиная с 9: n = 9, 16, 25, 36, 49... Но также ошибается и на n = 24, 30, 40... Для n = 40 ответ - 5, а ваш код дает 8.

Факториал растет намного быстрее квадрата, поэтому понятно, что правильный ответ может быть намного меньше, чем квадратный корень из n. А ваш вариант этого не допускает. На точных факториалах расхождение быстро станет гигантским. Для n = 7! = 5040 ответ - 7, а у вас - 72.
1
12.02.2018, 03:58
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.02.2018, 03:58
Привет! Вот еще темы с ответами:

Напечатать минимальное число, больше 500, которое нацело делится на 47 - C (СИ)
Напечатать минимальное число, больше 500, которое нацело делится на 47. Прошу написать на C(Без+) очень срочно.

Бинарным поиском найти максимальное a такое, что a^2 +3*a+2 - C (СИ)
Задание-2 Дано целое положительное n от 1 до 10^9. Бинарным поиском найти максимальное a такое, что a^2 +3*a+2&lt;=n. ВВОД : 10 ВЫВОД: 2...

Найти такое n, что в последовательности 1+1/n последнее число будет меньше заданного A - C (СИ)
Дано число a(1&lt;a&lt;=1,5). Найти такое меньшее n, что в последовательности чисел 1+1/2; 1+1/3;...; 1+1/n последнее число будет меньше a.

Найти все целые числа b, для которых а делится без остатка на b^2 и не делится без остатка на b^3 - C (СИ)
Пользователь вводит любое целое число а. Необходимо вывести все целые числа b , для которых а делится без остатка на b*b и не делится без...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru