Как найти сумму наибольшего нечетного множителя числа?

Question

У меня проблема с поиском суммы наибольшего нечетного множителя числа (F (x)) и F (x) = f (1) + f (2) + ... + f (x).Как известно, наибольшее значение 1 равно 1, 2 равно 1, 3 равно 3, 4 равно 1 и т. Д. *

Например, сумма наибольшего нечетного множителя числа 6 равна f (1) + f (2) + f (3) + f (4) + f (5) + f (6), то есть 1 + 1 + 3 + 1 + 5 + 3 или 14.

АЯ хочу попытаться решить число до 2 * 10 ^ 9

Так что это мой код для f (x), который получает 82/100 до истечения времени ожидания

unsigned long long int biggestOddFactor(unsigned long long int n){
    //!(n & (n - 1))
    while(n%2 == 0){
        n /= 2;
    }
    return n;
}

Этодругой метод, удаляющий ноль на последнем бите числа , но он дает только 77/100

#include <bitset>

unsigned long long int biggestOddFactorUsingBinary(unsigned long long int n){
    std::string bin = std::bitset<32>(n).to_string();
    int delet = 0;
    for(int i = bin.length()-1; i >= 0; i--){
        if(bin[i] == '0'){
            delet += 1;
        }else{
            break;
        }
    }
    bin = bin.substr(0, bin.length()-delet);
    return std::bitset<32>(bin).to_ulong();;
}

Есть ли способ оптимизировать мой алгоритм?

Answer 1

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

Например,Наибольший нечетный коэффициент каждого нечетного числа - это само число, и есть формула для суммы первых n нечетных чисел.Почему вы не используете это, чтобы вдвое сократить количество звонков biggestOddFactor?Это только для начала.

Наибольший коэффициент нечетности любого четного числа такой же, как и для половины этого числа.Таким образом, сумма наибольших нечетных факторов, скажем, 16, 14, 12 и 10 такая же, как для 8, 7, 6 и 5. И все же вы вычисляете эти два диапазона отдельно?Почему?

И так далее.Вам нужно оптимизировать свой алгоритм, а не реализацию плохого алгоритма.Приведенные выше концепции предлагают несколько возможных рекурсивных реализаций, которые будут намного быстрее.

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

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