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

@Jamshed · Регистрация: 06.01.2009

Студворк — интернет-сервис помощи студентам

УВАЖАЕМЫЕ ЭКСПЕРТЫ ПОМОГИТЕ РЕШИТЬ ЗАДАЧУ

(Время: 1 сек)
Пусть х — натуральное число. Назовем у его делителем, если 1 <= у <= х и остаток от деления х на у равен нулю.
Задано число х. Найдите количество его делителей, делящихся на каждое из простых чисел, на которое делится х.
Входные данные
Входной файл INPUT.TXT содержит целое число x (1 <= х <= 1018). Все простые делители числа х не превосходят тысячу.
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
№ INPUT.TXT OUTPUT.TXT
1 12 2
2 239 1

@Евгений 03 · 11.01.2020, 16:16

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std ;
 
 
 
int main()
{
 
    long long n , k = 0 , i ;
    cin >> n ;
    for (int i = 1 ; i <= sqrt(n) ; i++)
    {
        if (n % i == 0)
        {
            if (n / i != n / (n / i))
                k += 2 ;
            else
                k++ ;
        }
    }
    cout << k ;
    return 0 ;
}

Но это далеко не быстрый код

@AndryS1 · 11.01.2020, 17:50

Евгений 03, ваш код с перебором значений n от 0 до 100000000 в debug не превысил ни разу 1 секунду

@gunslinger · 12.01.2020, 00:27

Тут вполне можно использовать решето Эратосфена:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  bool sieve[MAX];
  int i, j, primecount = 0;
  __int64 prime[MAX];
 
  for (i = 0; i < MAX; i++)
    sieve[i] = 1;
  sieve[0] = sieve[1] = 0;
  for (i = 2; i < MAX; i++)
  {
    if (!sieve[i])
      continue;
    prime[primecount++] = i;
    for (j = i * i; j < MAX; j += i)
      sieve[j] = 0;
  }

где __int64 - это long long
а MAX задается через #define, например

C++
1
#define MAX 46349

Соответствующая тема: Функция: найти следующее простое число после заданного

В любом случае автора темы вряд ли через почти 11 лет интересует решение.

Новые блоги и статьи Все статьи Все блоги /
Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения anaschu 22.03.2026 e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git	1С: Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .	Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .	Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .
1С: Программный отбор элементов справочника по значению перечисления Maks 21.03.2026 Установка программного отбора элементов справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит значение перечислений. / / Событие "НачалоВыбора" реквизита на форме. . .	Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip

@Jamshed 0 / 0 / 0 Регистрация: 06.01.2009 Сообщений: 18

	Задано число х. Найдите количество его делителей, делящихся на каждое из простых чисел, на которое делится х. 08.02.2009, 07:39. Показов 5980. Ответов 3 Метки нет (Все метки) УВАЖАЕМЫЕ ЭКСПЕРТЫ ПОМОГИТЕ РЕШИТЬ ЗАДАЧУ (Время: 1 сек) Пусть х — натуральное число. Назовем у его делителем, если 1 <= у <= х и остаток от деления х на у равен нулю. Задано число х. Найдите количество его делителей, делящихся на каждое из простых чисел, на которое делится х. Входные данные Входной файл INPUT.TXT содержит целое число x (1 <= х <= 1018). Все простые делители числа х не превосходят тысячу. Выходные данные В выходной файл OUTPUT.TXT выведите ответ на задачу. Примеры № INPUT.TXT OUTPUT.TXT 1 12 2 2 239 1 0

@AndryS1 653 / 466 / 183 Регистрация: 23.04.2019 Сообщений: 1,987
	11.01.2020, 17:50
	Евгений 03, ваш код с перебором значений n от 0 до 100000000 в debug не превысил ни разу 1 секунду 0