Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.85
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
#1

МНОЖИТЕЛИ - C++

18.11.2010, 16:30. Просмотров 1592. Ответов 26
Метки нет (Все метки)

Какое минимальное число можно представить как произведение AxB ровно K способами.
AxB и ВxА считаются одним способом. К <= 50.
Пример:
вводится число К:
4
ответ:
24
1*24; 2*12; 3*8; 4*6; -----> 4 способа

Добавлено через 4 минуты
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
 
int main()
{
   int n = 1; // с какого числа начинаем
   int kF;    //найденое количество делителей
   int k;
   cin >> k; //количество способов
   while (1)
   {
      int i;
      kF = 0;
      for (i = 1; (i*i) <= n; i++)
            if (n%i == 0) kF++;   //находим делители
      if (kF == k) {cout << n << endl; break;} //если количество
      // делителей совпадает с нужным - выходим из цикла
      n++; // иначе переходим к следующему числу
   }
   cout << n << endl;
   return 0;
}
вот такое написал я ...
но для чисел К =37, 46, 47, 31 - решение найти не удалось
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.11.2010, 16:30     МНОЖИТЕЛИ
Посмотрите здесь:

Множители - C++
Здравствуйте! Друзья, помогите пожалуйста сделать не очень сложную ( для вас задачку) буду очень признателен ! Огромное спасибо! Дано...

Множители - C++
Дано количество способов разложить число на множители. Нужно узнать это число (наименьшее из них). Я использовал перебор чисел, для каждого...

Протые множители - C++
Помогите решить задачу Задача: разложить данное число на простые множители

Разложение на простые множители* - C++
Привет всем, помогите решить, если можно с комментариями что и как, буду очень благодарен, а то у нас курс как-то слишком быстро вперед...

Разложение в простые множители - C++
Дано натуральное число n. Требуется найти его разложение на простые множители. Формат выходных данных Требуется вывести строго...

Разложение числа на множители - C++
var s1,s2,n: longint; f: integer; begin write('vvedite natural chislo '); readln(n); f:=0; s1:=1; ...

Разложить на простые множители - C++
разложить целое число на простые множители (код на си)

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
18.11.2010, 16:37     МНОЖИТЕЛИ #2
Может потому что таких чисел не существует или они слишком большие?
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
18.11.2010, 16:40  [ТС]     МНОЖИТЕЛИ #3
Цитата Сообщение от Хохол Посмотреть сообщение
или они слишком большие?
в смысле 31!, 37!, 46!, 47! соответственно?
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
18.11.2010, 16:42     МНОЖИТЕЛИ #4
Нет, с чего бы. Просто очень большие. Или нет их вовсе.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.11.2010, 16:43     МНОЖИТЕЛИ #5
Mayonez, Все просто:
Если задано К, то что бы найти
минимальное число
, то нужно перемножить первые K-1 простые числа, это и будет ответ.
Нет, я свой ответ признаю ошибочным.
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
18.11.2010, 16:45  [ТС]     МНОЖИТЕЛИ #6
да, спасибо нашёл! Ответ valeriikozlov верный тут почитать
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.11.2010, 16:51     МНОЖИТЕЛИ #7
Mayonez, Не совсем верный мой был ответ. Но в голове крутится...
easybudda
Эксперт С++
9456 / 5469 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
18.11.2010, 22:40     МНОЖИТЕЛИ #8
Цитата Сообщение от Mayonez Посмотреть сообщение
в смысле 31!, 37!, 46!, 47! соответственно?
Абсолютно верно! Самое первое, что в голову приходит - факториал k. Гарантированно разделится на все числа от k до единицы. Но 50! слишком большое число...
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
18.11.2010, 22:55     МНОЖИТЕЛИ #9
easybudda, надо ровно k способами. С факториалами будет слишком много способов.
easybudda
Эксперт С++
9456 / 5469 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
19.11.2010, 01:05     МНОЖИТЕЛИ #10
вот так считает до 24 включительно
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
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
 
int test(uint64_t num, uint64_t div){
    if ( ! div )
        return 0;
    while ( div )
        if ( num % div-- )
            return 0;
    return 1;
}
 
void dump(uint64_t num, uint64_t div){
    uint64_t i;
    for ( i = 1; i <= div; ++i )
        printf("%llu * %llu = %llu\n", i, num / i, num);
}
 
#define TOP 1000000000LLU
 
int main(void){
    uint64_t num, k, m;
    
    printf("k = ");
    scanf("%llu", &k);
    
    for ( num = k * k, m = 0; m <= TOP; ++m ){
        if ( test(num + k * m, k) ){
            dump(num + k * m, k);
            break;
        }
    }
    
    if ( m > TOP )
        printf("Number too big!\n");
    
    return 0;
}
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.11.2010, 08:21     МНОЖИТЕЛИ #11
Цитата Сообщение от Хохол Посмотреть сообщение
Или нет их вовсе.
Такие числа точно существуют. Вот пример (я иду по степеням числа 2):
Число 2, К=1 (1*2)
Число 4, К=2 (1*4, 2*2)
Число 8, К=2 (1*8, 2*4)
Число 16, К=3 (1*16, 2*8, 4*4)
Число 32, К=3 (1*32, 2*16, 4*8)
Число 64, К=4 (1*64, 2*32, 4*16, 8*8)
Число 128, К=4 (1*128, 2*64, 4*32, 8*16)
Число 256, К=5 (1*256, 2*128, 4*64, 8*32, 16*16)
и т.д.
Получается что умножая на 4 любую степень 2, мы увеличиваем К на 1. Таким образом мы сможем получить и К =37, 46, 47, 31. Другой вопрос являются ли они минимальными? Но то что такие числа есть это точно.
easybudda
Эксперт С++
9456 / 5469 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
19.11.2010, 08:58     МНОЖИТЕЛИ #12
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Другой вопрос являются ли они минимальными?
не-а!
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Число 128, К=4 (1*128, 2*64, 4*32, 8*16)
При к = 4 минимальное число 24 было, немного меньше, чем 128
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.11.2010, 09:05     МНОЖИТЕЛИ #13
easybudda, Я знаю, это был ответ посвященный только существованию таких чисел и не более.
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
22.11.2010, 18:04  [ТС]     МНОЖИТЕЛИ #14
так всё-таки: решение существует но очень большое число или ...??
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.11.2010, 19:35     МНОЖИТЕЛИ #15
так всё-таки: решение существует но очень большое число или ...??
или решение тоже существует, но значение меньше. Если Вас все-таки интересует решение пишите в личку, подумаем вместе, я думаю решение найдем обязательно (потому что оно существует).
easybudda
Эксперт С++
9456 / 5469 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
22.11.2010, 19:39     МНОЖИТЕЛИ #16
Цитата Сообщение от Mayonez Посмотреть сообщение
решение существует но очень большое число или ...?
Мало того, существует как минимум два решения! valeriikozlov, и я Вам их озвучили. Другое дело, что так не самые маленькие из возможных чисел получаются, но делящиеся без остатка на нужное количество делителей. Кстати, программа, которую я написал, тоже не самое меньшее из возможных чисел выдаёт...

Добавлено через 59 секунд
Цитата Сообщение от valeriikozlov Посмотреть сообщение
я думаю решение найдем обязательно
ага... я уже тетрадку целую в 18 листов исписал - пока фигня какая-то получается, но чувствую, что где-то рядом...
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.11.2010, 20:24     МНОЖИТЕЛИ #17
Мало того, существует как минимум два решения!
На самом деле решений для каждого К бесконечно... То что я привел для степеней 2, точно так же распостраняется для степеней любого простого числа.

Цитата Сообщение от easybudda Посмотреть сообщение
Кстати, программа, которую я написал, тоже не самое меньшее из возможных чисел выдаёт...
Я знаю.

На самом деле решение есть, а это самое главное. Осталось "пустяк" - найти его.
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
22.11.2010, 20:45     МНОЖИТЕЛИ #18
Я что-то не пойму, разве количество делителей равно количеству способов? Что-то не въеду никак.
Пример:
вводится число К:
4
ответ:
24
1*24; 2*12; 3*8; 4*6; -----> 4 способа
4 способа,а делителей сколько? 8? или тоже четыре? Я насчитал 8,вот и не пойму. Или имеется ввиду простые множители? Тогда их три: 1,2,3. Всех остальных участников этих умножений в примере можно получить с помощью простых.
Автор,поясните.
Или я что-то недопонял,как всегда,или у автора ошибка тут
C++
1
 if (kF/2 == k) {cout << n << endl; break;} //если количество
А на два делить нужно поскольку количество множителей всегда кратно двум согласно условию (участие одного и того же элемента в разных перестановках исключено)

И ещё один момент: Если i увеличиваем до корня числа,то как мы найдём множитель 24 в случае,когда n==24? (как раз в случае приведённого примера). Поэтому проверять нужно, наверное, до самого числа,и делать ещё один вложенный цикл,отметая повторения,или что-то в этом духе. Или я опять ошибся
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.11.2010, 20:50     МНОЖИТЕЛИ #19
#pragma, Из условия:
AxB и ВxА считаются одним способом.
Значит то что Вы насчитали 8 делителей это хорошо и правильно - поэтому К равно 4.

Добавлено через 1 минуту
Цитата Сообщение от #pragma Посмотреть сообщение
А на два делить нужно поскольку количество множителей всегда кратно двум согласно условию (участие одного и того же элемента в разных перестановках исключено)
Цитата Сообщение от Mayonez Посмотреть сообщение
Какое минимальное число можно представить как произведение AxB ровно K способами.
К может быть и нечетным числом
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.11.2010, 21:15     МНОЖИТЕЛИ
Еще ссылки по теме:

Определить простые множители - C++
Задание: Составить программу определения, является ли данное число простым. Если число не является простым, то определить все его простые...

Разделить число на множители - C++
Нужно составить программу, в которой ты вводиш натуральное число, а она, если возможно, делит его на простые множители, тоесть 24=2*2*2*3...

Разложить число на простые множители - C++
Дано натуральное число n. Напечатать разложение этого числа на простые множители. Реализовать два варианта: 1) каждый простой множитель...

Разложить число на простые множители - C++
Если не трудно, можете найти где у меня ошибка, а то я новичок, никак не могу справится с этой задачкой: #include &lt;iostream&gt; using...

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


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

Или воспользуйтесь поиском по форуму:
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
22.11.2010, 21:15     МНОЖИТЕЛИ #20
Цитата Сообщение от valeriikozlov Посмотреть сообщение
А на два делить нужно поскольку количество множителей всегда кратно двум согласно условию (участие одного и того же элемента в разных перестановках исключено)
Какое минимальное число можно представить как произведение AxB ровно K способами.
#pragma,
К может быть и нечетным числом
Не вижу противоречия между двумя Вами приведёнными предложениями,так как "количество способов" != "количеству множителей" а автор в своём коде сравнивает их напрямую.
Ладно, спорить не буду, может, я прогнал просто

Добавлено через 12 минут
поправка: "количество способов" != "количеству простых делителей" - вот их и сравнивает автор.
Yandex
Объявления
22.11.2010, 21:15     МНОЖИТЕЛИ
Ответ Создать тему
Опции темы

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