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

поиск количества делителей чисел от 1 до N - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Программа, генерирующая 3 последовательности из 10-и случайных чисел http://www.cyberforum.ru/cpp-beginners/thread442688.html
Приветствую, уважаемые пользователи=) Помогите пожалуйста с задачкой, или покажите, где можно прочитать о этой функции, я не с компа(желательно линку дать прямую) Написать программу, которая генерирует три последовательности из 10-и случайных чисел в диапазоне от 1 до 10, и вывести каждую последовательность на экран. Вычеслить среднее арифметическое каждой последовательности.
C++ proc Описать функцию Arctg1(x, ε) вещественного типа (параметры x, ε — вещественные, |x| < 1, ε > 0), находящую приближенное значение функции arctg(x): arctg(x) = x – x3/3 + x5/5 – … + (–1)n·x2·n+1/(2·n+1) + … . В сумме учитывать все слагаемые, модуль которых больше ε. С помощью Arctg1 найти приближенное значение arctg(x) для данного x при шести дан-ных ε http://www.cyberforum.ru/cpp-beginners/thread442587.html
Описать функцию DigitN(K, N) C++
Описать функцию DigitN(K, N) целого типа, возвращающую N-ю циф-ру целого положительного числа K (цифры в числе нумеруются справа на-лево). Если количество цифр в числе K меньше N, то функция возвращает –1. Для каждого из пяти данных целых положительных чисел K1, K2, …, K5 вызвать функцию DigitN с параметром N, изменяющимся от 1 до 5.
C++ Описать функцию Sign(X)
Описать функцию Sign(X) целого типа, возвращающую для веществен-ного числа X следующие значения: –1, если X < 0; 0, если X = 0; 1, если X > 0. С помощью этой функции найти значение выражения Sign(A) + Sign(B) для данных вещественных чисел A и B.
C++ Два массива http://www.cyberforum.ru/cpp-beginners/thread442583.html
В массиве C(57) лежат целые числа. Сформировать новый массив B таким образом, чтобы в него вошли те элементы массива C, которые по модулю меньше числа 12. Заменить все отрицательные числа массива B на максимальное значение из массива C.
C++ Описать процедуру, вычисляющую вторую, тре-тью и четвертую степень числа Описать процедуру PowerA234(A, B, C, D), вычисляющую вторую, тре-тью и четвертую степень числа A и возвращающую эти степени соответст-венно в переменных B, C и D (A — входной, B, C, D — выходные парамет-ры; все параметры являются вещественными). С помощью этой процедуры найти вторую, третью и четвертую степень пяти данных чисел. Барышня, Вы бы хоть названия своим темам поразнообразнее... подробнее

Показать сообщение отдельно
AC-93
13 / 13 / 0
Регистрация: 27.01.2010
Сообщений: 150
08.02.2012, 07:10     поиск количества делителей чисел от 1 до N
итак задача
нужно посчитать кол-во чисел с одинаковым количество делителей, взять число перестановок, все перемножить, отнять единицу.
хранить кол-во чисел с кол-вом делителей можно в массиве (назовем его DEL) (кол-во делителей оценивается для больших N как корень третьей степени, т.е. тут максимум 2600 массив понадобится).
проблема как отыскать сколько у какого числа делителей.
пока придумал только такой вариант, читаем все входные, запоминаем порядок чисел, сортируем по возрастанию.
далее генерируем DEL , т.е. 2*10^9 слишком много, то можно использовать ползущий массив, который например по 100000 будет захватывать, а вычислять таким образом: берем каждое число по порядку (например i) и все n*i < верхней границы помечаем ++ делителей. т.е. взяли 5, пометили что там 1, потом 10 ++ , потом 15 и тд. когда достигаем числа из условий -считаем и выводим. Получается вроде как n*ln(n) сложность. Но прикинул- не проходит.
А какие еще варианты улучшения могут быть?

Добавлено через 7 минут
Просьба не писать код, т.к. все-таки контест длится и кто-то может обидеться, но указать куда копать.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 08:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru