Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
emilgaziev
0 / 0 / 0
Регистрация: 25.01.2018
Сообщений: 3
1

Найти минимальное x, такое что x! делится на n

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

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

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

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

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

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

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

12
Hitoku
Модератор
1703 / 1302 / 1400
Регистрация: 28.10.2016
Сообщений: 4,240
Завершенные тесты: 4
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Эксперт С++
4608 / 2422 / 674
Регистрация: 18.10.2014
Сообщений: 4,133
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
18318 / 12029 / 2506
Регистрация: 24.12.2010
Сообщений: 24,293
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Эксперт С++
4608 / 2422 / 674
Регистрация: 18.10.2014
Сообщений: 4,133
10.02.2018, 15:09 6
Цитата Сообщение от Байт Посмотреть сообщение
Но идея, надеюсь, понятна...
Не понятно только, какое отношение предложенный цикл имеет к нахождению этого числа yp. В чем идея? В чем смысл деления показателя степени на основание степени?
0
Байт
Эксперт C
18318 / 12029 / 2506
Регистрация: 24.12.2010
Сообщений: 24,293
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Эксперт С++
4608 / 2422 / 674
Регистрация: 18.10.2014
Сообщений: 4,133
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
18318 / 12029 / 2506
Регистрация: 24.12.2010
Сообщений: 24,293
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Эксперт С++
4608 / 2422 / 674
Регистрация: 18.10.2014
Сообщений: 4,133
10.02.2018, 17:44 10
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
это попытка вывести формулу Лагранжа.
Лежандра. Блин. Лежандра.
0
easybudda
Модератор
Эксперт CЭксперт С++
10090 / 6001 / 1503
Регистрация: 25.07.2009
Сообщений: 11,379
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
18318 / 12029 / 2506
Регистрация: 24.12.2010
Сообщений: 24,293
11.02.2018, 12:03 12
easybudda, Мне кажется, что для n=125 ваш код даст ответ 25. В то время как i = 15 уже подходит.
Или, скажем, n= 250...
Хотя придумывание примеров, опровергающих ваш код, - тоже интересная задача
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4608 / 2422 / 674
Регистрация: 18.10.2014
Сообщений: 4,133
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

Минимальное число больше 1000,которое нацело делится на 15
найти минимальное число больше 1000,которое нацело делится на 15. на си...

Напечатать минимальное число, больше 500, которое нацело делится на 47
Напечатать минимальное число, больше 500, которое нацело делится на 47. Прошу...

Бинарным поиском найти максимальное a такое, что a^2 +3*a+2
Задание-2 Дано целое положительное n от 1 до 10^9. Бинарным поиском найти...


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

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

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