Поменять местами два числа в массиве, которые имеют наибольшее количество делителей

@Alexey_Kursk · Регистрация: 11.10.2023

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

Дан массив из 12 натуральных целых чисел. Поменять местами два числа, которые имеют наибольшее количество делителей.
Значения в массив вводятся с клавиатуры

@Volga_ · 22.10.2023, 17:04

Alexey_Kursk, можно использовать следующую функцию для нахождения количества делителей числа:

C++

int f(int n) 
{
    int res = 1;
    for (int i = 2; i <= n / 2 + 1; i++)
        if (n % i == 0) res++;
    return res + 1;
}

@ram876 · 22.10.2023, 18:03

Ноль тоже можно считать натуральным числом и у него делитель любое число кроме нуля. Это как то надо учитывать?

@Alexey_Kursk · 22.10.2023, 18:15 **[ТС]**

0 учитывать не нужно

@igorrr37 · 23.10.2023, 06:46

Пусть N - число, кол-во делителей которого надо найти. Решетом создаём массив всех простых от 2 до sqrt(N). С помощью этого массива раскладываем N на произведение простых делителей. Находим кол-во всех сочетаний найденных простых делителей.

C++

#include <iostream>
#include <unordered_map>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <list>
#include <forward_list>
#include <vector>
#include <climits>
#include <random>
#include <ctime>
 
int main()
{
    int num = 2e9; // число, делители которого ищем
 
    std::vector<int> vPrimes((int)std::sqrt(INT_MAX));
    std::iota(vPrimes.begin(), vPrimes.end(), 2);
 
    // решето Эратосфена
    int ind{};
    for (int i = 2; i < vPrimes.size(); i += 2) // для 2
    {
        vPrimes[i] = 0;
    }
    for (int i = 1; i < vPrimes.size() && ind < vPrimes.size(); ++i) // для > 2
    {
        int p = vPrimes[i];
        if (!p)
            continue;
        ind = p * p - 2;
        int step = 2 * p;
        for (int j = ind; j < vPrimes.size(); j += step)
        {
            vPrimes[j] = 0;
        }
    }
 
    std::mt19937 eng{(unsigned)time(nullptr)};
    std::uniform_int_distribution uid{(int)2, (int)2e9};
 
    while (true)
    {
        num = uid(eng);
        int tmpNum = num;
        std::unordered_map<int, int> ump;
        for (int i = 0; tmpNum != 1 && i < vPrimes.size(); ++i)
        {
            if (vPrimes[i] == 0)
                continue;
            while (tmpNum % vPrimes[i] == 0)
            {
                tmpNum /= vPrimes[i];
                ++ump[vPrimes[i]];
            }
        }
        if (tmpNum != 1)
            ++ump[tmpNum];
 
        // кол-во всех сочетаний простых делителей
        int cnt{ 1 };
        for (auto const& [k, v] : ump)
        {
            cnt *= v + 1;
        }
        std::cout << cnt << "\n";
 
        // наивный алгоритм для проверки
        int sqrtNum = std::sqrt(num);
        int cntNaiv = (sqrtNum * sqrtNum == num ? 1 : 2);
        for (int i = 2; i <= sqrtNum; ++i)
        {
            if (num % i == 0)
            {
                cntNaiv += 2;
            }
        }
        std::cout << cntNaiv << "\n";
        
        if (cnt != cntNaiv)
        {
            std::cerr << "Error: " << num << "\n";
            break;
        }
    }
}

Добавлено через 8 минут
Volga_, можно ускорить если идти до корня а не до n/2

C++

int sqrtNum = std::sqrt(num);
int cntNaiv = (sqrtNum * sqrtNum == num ? 1 : 2);
for (int i = 2; i <= sqrtNum; ++i)
{
    if (num % i == 0)
    {
        cntNaiv += 2;
    }
}
std::cout << cntNaiv << "\n";

@igorrr37 · 23.10.2023, 08:06

Но при большом количестве запросов решето быстрей чем даже корень из N

@TheCalligrapher · 23.10.2023, 08:50

Сообщение от igorrr37

Но при большом количестве запросов решето быстрей чем даже корень из N

Ключевой момент здесь - нахождение количества делителей через факторизацию, а не через перебор всевозможных делителей. А уже делать ли факторизацию с решетом или без... не так важно.

Более того, если оптимизировать поиск делителей вот так Получить все простые делители числа, это наверное, даст чуть ли не ту же самую практическую эффективность, чем заранее построенное решето.

Добавлено через 33 минуты

C++

unsigned num_of_divisors(unsigned long long v)
{
  unsigned nod = 1;
 
  unsigned long long r = std::sqrt(v);
  
  for (unsigned d : { 2, 3, 5, 7 })
    if (v % d == 0)
    {
      unsigned m = 2;
      for (v /= d; v % d == 0; v /= d, ++m);
      nod *= m;
    }
 
  for (unsigned long long d = 11; d <= r;)
  {
    for (unsigned a : 
           { 
             2, 4, 2, 4, 6, 2, 6, 4, 
             2, 4, 6, 6, 2, 6, 4, 2, 
             6, 4, 6, 8, 4, 2, 4, 2, 
             4, 8, 6, 4, 6, 2, 4, 6, 
             2, 6, 6, 4, 2, 4, 6, 2, 
             6, 4, 2, 4, 2, 10, 2, 10
           })
    {
      if (v % d == 0)
      {
        unsigned m = 2;
        for (v /= d; v % d == 0; v /= d, ++m);
        nod *= m;
      }
      
      d += a;
    }
  }
    
  if (v != 1)
    nod *= 2;
 
  return nod;
}

@igorrr37 · 23.10.2023, 10:22

TheCalligrapher, потестил. Твой алгос лучше наивного, но до решета не дотягивает. Вот времена и тестовая прога. Может напутал чего

C++

#include <iostream>
#include <unordered_map>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <list>
#include <forward_list>
#include <vector>
#include <climits>
#include <random>
#include <ctime>
#include <chrono>
 
int main()
{
    int num = 2e9; // число, делители которого ищем
 
    std::vector<int> vPrimes((int)std::sqrt(INT_MAX));
    std::iota(vPrimes.begin(), vPrimes.end(), 2);
 
    // построение решета Эратосфена
    int ind{};
    for (int i = 2; i < vPrimes.size(); i += 2) // для 2
    {
        vPrimes[i] = 0;
    }
    for (int i = 1; i < vPrimes.size() && ind < vPrimes.size(); ++i) // для > 2
    {
        int p = vPrimes[i];
        if (!p)
            continue;
        ind = p * p - 2;
        int step = 2 * p;
        for (int j = ind; j < vPrimes.size(); j += step)
        {
            vPrimes[j] = 0;
        }
    }
    vPrimes.erase(std::remove(vPrimes.begin(), vPrimes.end(), 0), vPrimes.end());
 
    std::mt19937 eng{(unsigned)time(nullptr)};
    std::uniform_int_distribution uid{(int)2, (int)2e9};
    std::unordered_map<int, int> ump;
    int testLim = 1e4; // кол-во запросов
    while (true)
    {
        num = uid(eng);
        int cntErat{}, cntNaiv{}, cntCallig{};
 
        // алгоритм решето тест
        auto time1 = std::chrono::high_resolution_clock::now();
        for (int i = 0; i < testLim; ++i)
        {
            int tmpNum = num;
            for (auto it = vPrimes.begin(); tmpNum >= *it * *it; ++it)
            {
                while (tmpNum % *it == 0)
                {
                    tmpNum /= *it;
                    ++ump[*it];
                }
            }
            if (tmpNum != 1)
                ++ump[tmpNum];
 
            // кол-во всех сочетаний простых делителей
            cntErat = 1;
            for (auto const& [k, v] : ump)
            {
                cntErat *= v + 1;
            }
            //std::cout << cntErat << "\n";
            ump.clear();
        }
        auto time2 = std::chrono::high_resolution_clock::now();
 
        // алгоритм TheCalligrapher тест
        for (int i = 0; i < testLim; ++i)
        {
            int tmpNum = num;
            cntCallig = 1;
            unsigned long long r = std::sqrt(tmpNum);
 
            for (unsigned d : { 2, 3, 5, 7 })
                if (tmpNum % d == 0)
                {
                    unsigned m = 2;
                    for (tmpNum /= d; tmpNum % d == 0; tmpNum /= d, ++m);
                    cntCallig *= m;
                }
 
            for (unsigned long long d = 11; d <= r;)
            {
                for (unsigned a :
                {
                    2, 4, 2, 4, 6, 2, 6, 4,
                        2, 4, 6, 6, 2, 6, 4, 2,
                        6, 4, 6, 8, 4, 2, 4, 2,
                        4, 8, 6, 4, 6, 2, 4, 6,
                        2, 6, 6, 4, 2, 4, 6, 2,
                        6, 4, 2, 4, 2, 10, 2, 10
                })
                {
                    if (tmpNum % d == 0)
                    {
                        unsigned m = 2;
                        for (tmpNum /= d; tmpNum % d == 0; tmpNum /= d, ++m);
                        cntCallig *= m;
                    }
                    d += a;
                }
            }
 
            if (tmpNum != 1)
                cntCallig *= 2;
        }
        auto time3 = std::chrono::high_resolution_clock::now();
 
        // наивный алгоритм тест
        for (int i = 0; i < testLim; ++i)
        {
            int sqrtNum = std::sqrt(num);
            cntNaiv = (sqrtNum * sqrtNum == num ? 1 : 2);
            for (int i = 2; i <= sqrtNum; ++i)
            {
                if (num % i == 0)
                {
                    cntNaiv += 2;
                }
            }
            //std::cout << cntNaiv << "\n";
        }
        auto time4 = std::chrono::high_resolution_clock::now();
 
        std::cout 
            << std::chrono::duration_cast<std::chrono::milliseconds>(time2 - time1).count() << "  "
            << std::chrono::duration_cast<std::chrono::milliseconds>(time3 - time2).count() << "  "
            << std::chrono::duration_cast<std::chrono::milliseconds>(time4 - time3).count() << "\n";
        
        if (cntErat != cntNaiv || cntCallig != cntNaiv)
        {
            std::cerr << "Error: " << num << "\n";
            break;
        }
    }
}

@TheCalligrapher · 24.10.2023, 05:43

Сообщение от igorrr37

Твой алгос лучше наивного, но до решета не дотягивает.

Я сделал глупость в своей реализации. Вычислять r = std::sqrt(v); заранее и потом проверять до этого r - это, конечно же, чушь полнейшая.

Правильно:

C++

unsigned num_of_divisors(unsigned long long v)
{
  unsigned nod = 1;
 
  for (unsigned d : { 2, 3, 5, 7 })
    if (v % d == 0)
    {
      unsigned m = 2;
      for (v /= d; v % d == 0; v /= d, ++m);
      nod *= m;
    }
 
  for (unsigned long long d = 11; d * d <= v;)
  {
    for (unsigned a : 
           { 
             2, 4, 2, 4, 6, 2, 6, 4, 
             2, 4, 6, 6, 2, 6, 4, 2, 
             6, 4, 6, 8, 4, 2, 4, 2, 
             4, 8, 6, 4, 6, 2, 4, 6, 
             2, 6, 6, 4, 2, 4, 6, 2, 
             6, 4, 2, 4, 2, 10, 2, 10
           })
    {
      if (v % d == 0)
      {
        unsigned m = 2;
        for (v /= d; v % d == 0; v /= d, ++m);
        nod *= m;
      }
      
      d += a;
    }
  }
    
  if (v != 1)
    nod *= 2;
 
  return nod;
}

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

Новые блоги и статьи
Элементы алгоритмизации hw_wired 28.01.2025 Основы алгоритмизации В современном мире алгоритмы играют фундаментальную роль в развитии информационных технологий и программирования. Понимание основ алгоритмизации является ключевым элементом в. . .	Человек и информация hw_wired 28.01.2025 Введение: роль информации в познании мира В современном мире информация играет фундаментальную роль в процессе познания окружающей действительности. Она представляет собой совокупность сведений об. . .	Компьютер и информация hw_wired 28.01.2025 Эволюция вычислительных машин История развития вычислительной техники начинается задолго до появления первых электронных устройств. Человечество всегда стремилось упростить процесс вычислений и. . .	Информационные технологии hw_wired 28.01.2025 Введение в современные технологии работы с информацией В современном мире информационные технологии стали неотъемлемой частью практически всех сфер человеческой деятельности. Они существенно. . .	Информация вокруг нас hw_wired 28.01.2025 Основные понятия информации В современном мире понятие информации является фундаментальным и охватывает практически все сферы человеческой деятельности. Информация представляет собой совокупность. . .	Компьютер для начинающих hw_wired 28.01.2025 Введение в мир компьютерных технологий В современном мире информация стала одним из важнейших ресурсов человечества, определяющим развитие общества и технологий. Наша жизнь неразрывно связана с. . .
[golang] 189. Rotate Array alhaos 28.01.2025 Повороты рукоятки, целочисленный слайс нужно сдвинуть на целое положительное число. Мне очень нравится решение на GO / / https:/ / leetcode. com/ studyplan/ top-interview-150/ package topInterview . . .	КуМир: решение задач на матрицы bytestream 28.01.2025 КуМир представляет собой среду для обучения программированию, которая включает в себя мощные инструменты для работы с матрицами. Матрица в программировании - это двумерный массив, состоящий из. . .	КуМир: решение задач на строки bytestream 28.01.2025 В системе программирования КуМир работа со строковыми данными является одним из важнейших аспектов создания программ. Строки представляют собой последовательности символов, заключенные в кавычки,. . .	КуМир: решение геометрических задач bytestream 28.01.2025 Программирование геометрических задач в среде КуМир становится всё более актуальным в обучении школьников и студентов. КуМир — это разработанная в России обучающая программная среда, предназначенная. . .	КуМир, исполнитель Водолей: Задачи и решения bytestream 28.01.2025 КуМир — это образовательная среда для обучения программированию. Она предлагает пользователям разнообразные инструменты для разработки и отладки программ, что особенно ценно для студентов и. . .	КуМир, исполнитель Чертежник: Решение задач bytestream 28.01.2025 КуМир (Комплект Учебных МИРов) представляет собой образовательную среду для обучения основам программирования и алгоритмизации. Исполнитель Чертежник работает на координатной плоскости, где может. . .

@Alexey_Kursk 0 / 0 / 0 Регистрация: 11.10.2023 Сообщений: 13
		1
	Поменять местами два числа в массиве, которые имеют наибольшее количество делителей 22.10.2023, 16:46. Показов 581. Ответов 8 Метки #с++, 1 курс (Все метки) Дан массив из 12 натуральных целых чисел. Поменять местами два числа, которые имеют наибольшее количество делителей. Значения в массив вводятся с клавиатуры 0

@ram876 758 / 455 / 213 Регистрация: 19.12.2016 Сообщений: 1,815
	22.10.2023, 18:03	3
	Ноль тоже можно считать натуральным числом и у него делитель любое число кроме нуля. Это как то надо учитывать? 0

@Alexey_Kursk 0 / 0 / 0 Регистрация: 11.10.2023 Сообщений: 13
	22.10.2023, 18:15 [ТС]	4
	0 учитывать не нужно 0

@igorrr37 2862 / 2010 / 988 Регистрация: 21.12.2010 Сообщений: 3,716 Записей в блоге: 15
	23.10.2023, 08:06	6
	Но при большом количестве запросов решето быстрей чем даже корень из N Миниатюры 0

	24.10.2023, 05:43