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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 32, средняя оценка - 4.97
mikelll
15 / 15 / 1
Регистрация: 27.12.2010
Сообщений: 153
#1

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

09.11.2012, 15:17. Просмотров 4634. Ответов 7
Метки нет (Все метки)

Нужно узнать количество делителей числа N.
Но сложность в том что N большое и перебирать все делите не вариант.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.11.2012, 15:17
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти количество делителей заданного числа n, заданного в диапазоне 1 <= n <= 10^18 (C++):

Для заданного натурального числа N найти количество его делителей - C++
Разработать функцию, которая для заданного натурального числа N возвращает количество его делителей. С помощью данной функции вывести на...

Определить количество делителей заданного числа - C++
Создайте программу которая будет вычислять сколько у числа делителей .И что бы она поддерживала числа до 999966000289.

Разработать функцию, которая для заданного натурального числа N возвращает количество его делителей - C++
И с помощью этой функции для заданного числа A вывести на экран следующее по отношению к нему число, имеющее столько же делителей, сколько...

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

Найти первую и последнюю цифры заданного числа; найти сумму цифр заданного числа - C++
Помогите решить в С++ 2.1 Дано натуральное число: − найти первую и последнюю цифры числа; − верно ли, что сумма цифр данного числа...

Рекурсия: вывод всех делителей заданного числа - C++
Помогите, Написать программу которая выводить все делители заданного числа. Рекурсией!!!

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.11.2012, 15:35 #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. Более быстрые алгоритмы уже не так тривиальны.
1
mikelll
15 / 15 / 1
Регистрация: 27.12.2010
Сообщений: 153
09.11.2012, 15:46  [ТС] #3
Да вот 1 <= n <= 10^18
и тут по ходу в никакие типы не влезает =(
0
JlightenDev_C++
61 / 61 / 7
Регистрация: 12.08.2012
Сообщений: 150
09.11.2012, 15:52 #4
Цитата Сообщение от mikelll Посмотреть сообщение
Да вот 1 <= n <= 10^18
и тут по ходу в никакие типы не влезает =(
unsigned long long n;
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.11.2012, 15:58 #5
Ну, тут мне уже писать код не хочется, но алгоритм мне видится таким: берем какой-нибудь быстрый алгоритм факторизации со сложностью O(n ^ (1/3) ) или быстрее, и затем, зная факторизацию, можно с помощью комбинаторики подсчитать количество делителей.
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
09.11.2012, 18:23 #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 на простые множители, посчитать сколько раз встречается каждое простое число в разложении и перемножить соотвествующие результаты в соответствии с вышеприведенной формулой.


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

return res + 2 - (n == 1);
0
zer0mail
2334 / 1960 / 192
Регистрация: 03.07.2012
Сообщений: 7,029
Записей в блоге: 1
12.09.2016, 13:32 #8
Цитата Сообщение от ShuricFC Посмотреть сообщение
а что значат эти две строчки?
Дату постов посмотрите.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.09.2016, 13:32
Привет! Вот еще темы с ответами:

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

Найти количество четных цифр заданного натурального числа - C++
Привет, всем))помогите пожалуйста написать код для задачи: найти количество четных цифр заданного натурального числа. вот мой код,но он...

Найти количество и сумму цифр заданного натурального числа - C++
Дано натуральное число n. Используя операции деления нацело и взятия остатка от деления, найти количество и сумму его цифр.

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
12.09.2016, 13:32
Ответ Создать тему
Опции темы

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