Количество чисел n, у которых число делителей равно числу делителей n+1

#c_sharp #алгоритм #простые_числа #факторизация

Сама задача на первый взгляд кажется довольно простой:


  Найти количество таких чисел n (n<10^5), у которых число делителей равно числу
делителей числа n+1


Вот мое решение:  

static int NumberOfDividers(int number)
        {
            int counter = 0;
            for (int i = 1; i <= number; i++)
                if (number % i == 0)
                    counter++;
            return counter;

        }
        static void Main()
        {
            int counter = 0;
            for (int i = 1; i < 100000; i++)
            {
                if (NumberOfDividers(i) == NumberOfDividers(i + 1))
                    counter++;
            }
            Console.WriteLine(counter);
        }


Но алгоритм работает очень долго, какие есть варианты для его упрощения?
    

Ответы

Ответ 1

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

void Main()
{
    int counter = 0;
    int current = 0;
    for (int i = 1; i < 100000; i++)
    {
        int next = NumberOfDividers(i);
        if (current == next)
        {
            counter++;
        }
        current = next;
    }
    Console.WriteLine(counter);//10585 
}


Только это изменение уменьшит время работы вдвое.

Теперь разберемся с вычислением количества делителей.

Любое число делится на 1 и себя, поэтому сразу запишем 2 в счетчик, или 0, если это
единица.

static int NumberOfDividers(int number)
{
    int counter = number == 1 ? 0 : 2;


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

    double root = Math.Sqrt(number);


Если число является квадратом, то один из делителей будет равен корню, проверяем
и добавляем единицу в счетчик остальные делители парные. Для проверки нужна только
целая часть корня, иначе при сравнении мы никогда не получим равенства (см. этот вопрос-ответ).
Кроме того, если исходное число - единица, эта проверка добавит в счетчик ее единственный
делитель и функция вернет 1, как и должна.

    int intRoot = (int)root;
    if(intRoot * intRoot  == number)
        counter++;


Остался основной цикл. Начинаем с 2, т.к. единица и само число уже учтены. Делители
ходят парами, поэтому счетчик увеличиваем на 2. Исключением является корень из числа,
но его мы уже учли.

    for (int i = 2; i < root; i++)
        if (number % i == 0)
        {
            counter +=2;//делители ходят парами. поэтому увеличиваем сразу на два.
        }
    return counter;
}


После всех манипуляций суммарное время выполнения, по грубым замерам*, уменьшилось
с ~3 минут до ~0,4 секунды. Т.е. примерно в 450(!) раз.



*стандартный тестовый стенд не собирал, данные со встроенного счетчика времени LiNQPad


Ответ 2

Я прошу прощения, но на C# пас. Зато могу набросать на C++ :)

Итак, чтобы посчитать количество делителей - раскладываем число на простые сомножители;
количество делителей после этого определяется как... как в этом ответе :) - там расписано.

Искать делители просто - достаточно проверять простые числа до квадратного корня
из числа, причем само число всякий раз уменьшаем делением на найденный простой делитель
- для скорости. Быстрый квадратный корень передираем у Уоррена в "Алгоритмических трюках";
но можно использовать и обычный sqrt.

Считаем для каждого числа один раз, запоминая значение для предыдущего числа. 

Все, собирая все вместе - 

#include 
#include 
#include