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

Найти количество делителей заданного числа n, заданного в диапазоне 1 <= n <= 10^18 - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 32, средняя оценка - 4.97
mikelll
 Аватар для mikelll
15 / 15 / 1
Регистрация: 27.12.2010
Сообщений: 153
09.11.2012, 15:17     Найти количество делителей заданного числа n, заданного в диапазоне 1 <= n <= 10^18 #1
Нужно узнать количество делителей числа N.
Но сложность в том что N большое и перебирать все делите не вариант.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.11.2012, 15:17     Найти количество делителей заданного числа n, заданного в диапазоне 1 <= n <= 10^18
Посмотрите здесь:

C++ Рекурсия: вывод всех делителей заданного числа
C++ Разработать функцию, которая для заданного натурального числа N возвращает количество его делителей
C++ Найти количество четных цифр заданного натурального числа
Найти количество четных цифр заданного натурального числа C++
Для заданного натурального числа N найти количество его делителей C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.11.2012, 15:35     Найти количество делителей заданного числа n, заданного в диапазоне 1 <= n <= 10^18 #2
Насколько большое N?
Как вариант, простейший алгоритм за O(sqrt(n)).
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
 
int count_of_divisors(int n)
{
    int res = 0;
 
    for (int i = 2; i * i <= n; ++i)
        if (n % i == 0)
            res += 2 - (i *i == n);
 
    return res + 2 - (n == 1);
}
 
int main()
{
    std::cout << count_of_divisors(5040) << std::endl;
}
Будет укладываться в секунду для чисел примерно до 10^13. Более быстрые алгоритмы уже не так тривиальны.
mikelll
 Аватар для mikelll
15 / 15 / 1
Регистрация: 27.12.2010
Сообщений: 153
09.11.2012, 15:46  [ТС]     Найти количество делителей заданного числа n, заданного в диапазоне 1 <= n <= 10^18 #3
Да вот 1 <= n <= 10^18
и тут по ходу в никакие типы не влезает =(
JlightenDev_C++
 Аватар для JlightenDev_C++
61 / 61 / 7
Регистрация: 12.08.2012
Сообщений: 150
09.11.2012, 15:52     Найти количество делителей заданного числа n, заданного в диапазоне 1 <= n <= 10^18 #4
Цитата Сообщение от mikelll Посмотреть сообщение
Да вот 1 <= n <= 10^18
и тут по ходу в никакие типы не влезает =(
unsigned long long n;
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.11.2012, 15:58     Найти количество делителей заданного числа n, заданного в диапазоне 1 <= n <= 10^18 #5
Ну, тут мне уже писать код не хочется, но алгоритм мне видится таким: берем какой-нибудь быстрый алгоритм факторизации со сложностью O(n ^ (1/3) ) или быстрее, и затем, зная факторизацию, можно с помощью комбинаторики подсчитать количество делителей.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
09.11.2012, 18:23     Найти количество делителей заданного числа n, заданного в диапазоне 1 <= n <= 10^18 #6
Для решения данной задачи мы воспользуемся одной из теорем комбинаторики.

Теорема. Если существует K классов, содержащих соответственно n1 , n2 , . . . nK элементов, то число различных способов выбора элементов равно (n1 + 1)(n2 + 1)...(nK + 1)

Для определенности рассмотрим на примере. В коробке лежат 10 шаров синего, 8 красного и 5 желтого цветов. Сколькими способами можно достать данные шары из коробки? Разумеется, что все шары доставать необязательно, например, можно достать 2 синих, 4 желтых и 3 красных шара, или 1 синий и 5 желтых. А ведь можно и вообще их не доставать, этот случай тоже является случаем выбора шаров, в результате которого получается пустое множество выбранных элементов.

Для ответа на этот вопрос следует воспользоваться вышеприведенной теоремой. Мы имеем три класса:
Шары синего
Желтого
Красного цветов

Число элементов первого класса равно 10, второго - 8, третьего, соответственно, 5. Тогда общее количество возможных вариантов выбора будет равно S = (10 + 1)(8 + 1)(5 + 1) = 594. То есть число различных способов выбора шаров из коробки равно 594.

Эту задачу можно было бы решать и методом полного перебора, что значительно увеличит время выполнения программы.

Теперь проведем аналогию между нашей задачей и задачей про шары. Основная теорема арифметики гласит, что любое натуральное число можно представить в виде произведения простых чисел, входящих в разложение данного числа в различных степенях. Классом в нашем случае является простое число. Количеством элементов - степень, в которой это число входит в разложение.

Тогда для решения задачи необходимо разложить число x на простые множители, посчитать сколько раз встречается каждое простое число в разложении и перемножить соотвествующие результаты в соответствии с вышеприведенной формулой.


Взял с ******** могу показать код, только он на паскале.
ShuricFC
0 / 0 / 0
Регистрация: 08.09.2016
Сообщений: 73
12.09.2016, 10:09     Найти количество делителей заданного числа n, заданного в диапазоне 1 <= n <= 10^18 #7
а что значат эти две строчки? res += 2 - (i *i == n);

return res + 2 - (n == 1);
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.09.2016, 13:32     Найти количество делителей заданного числа n, заданного в диапазоне 1 <= n <= 10^18
Еще ссылки по теме:

C++ Определить количество делителей заданного числа
Найти количество элементов массива меньших заданного числа C++
Найти все натуральные числа из заданного промежутка, с заданным количеством делителей C++

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

Или воспользуйтесь поиском по форуму:
zer0mail
2188 / 1871 / 187
Регистрация: 03.07.2012
Сообщений: 6,661
Записей в блоге: 1
12.09.2016, 13:32     Найти количество делителей заданного числа n, заданного в диапазоне 1 <= n <= 10^18 #8
Цитата Сообщение от ShuricFC Посмотреть сообщение
а что значат эти две строчки?
Дату постов посмотрите.
Yandex
Объявления
12.09.2016, 13:32     Найти количество делителей заданного числа n, заданного в диапазоне 1 <= n <= 10^18
Ответ Создать тему
Опции темы

Текущее время: 23:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru