сумма множителей в заданном диапазоне

Question

хорошо, я хочу суммировать кратные 3 и 5. Не слишком сложно, если я хочу просто сумму на данное число, например -> до 60, сумма равна 870.

Но что если я хочу только первые 15 кратных?

один из способов -

void summation (const unsigned long number_n, unsigned long &summe,unsigned int &counter );
void summation (const unsigned long number_n, unsigned long &summe,unsigned int &counter )
{

       unsigned int howoften = 0;
       summe = 0;
       for( unsigned long i = 1; i <=number_n; i++ )
           if (howoften <= counter-1)
           {
               if( !( i % 3 ) || !( i % 5 ) )
               {
                   summe += i;
                   howoften++;
               }
           }
       counter = howoften;



   return;
}

Но, как и ожидалось, время выполнения не приемлемо для счетчика типа 1.500.000: - /

Хм, я много чего пробовал, но не могу найти решение самостоятельно.

Я также попробовал более быстрый алгоритм суммирования, такой как (не волнуйтесь о переполнении в данный момент):

int sum(int N);
int sum(int N)
{
    int S1, S2, S3;

    S1 = ((N / 3)) * (2 * 3 + (N / 3 - 1) * 3) / 2;
    S2 = ((N / 5)) * (2 * 5 + (N / 5 - 1) * 5) / 2;
    S3 = ((N / 15)) *(2 * 15 + (N / 15 - 1) * 15) / 2;

    return S1 + S2 - S3;
}

или даже

unsigned long sum1000 (unsigned long target);
unsigned long sum1000 (unsigned long target)
{
   unsigned int summe = 0;
   for (unsigned long i = 0; i<=target; i+=3) summe+=i;
   for (unsigned long i = 0; i<=target; i+=5) summe+=i;
   for (unsigned long i = 0; i<=target; i+=15) summe-=i;
return summe;

}

Но я недостаточно умен, чтобы настроить достаточно быстрый алгоритм (я говорю, что 5-10 се c. Все в порядке)

вся сумма кратных не моя проблема, первые N кратные:)

Спасибо за чтение, и если у вас есть какие-либо идеи, было бы здорово

Answer 1

Некоторые предварительные условия:

(не волнуйтесь о переполнении в этой точке)

Хорошо, так что давайте проигнорируем это полностью.

Далее сумма всех чисел от 1 до n может быть рассчитана из (см., например, здесь ):

int sum(int n) {
    return  (n * (n+1)) / 2;
}

Обратите внимание, что n*(n+1) является четным числом для любого n, поэтому использование целочисленной артистики для /2 не является проблемой.

Как это помогает получить сумму чисел, делимых на 3? Начнем с четных чисел (делится на 2). Мы выпишем длинную форму суммы выше:

1 + 2 + 3 + 4 + ... + n

умножим каждый член на 2:

2 + 4 + 6 + 8 + ... + 2*n

Теперь я надеюсь, вы видите, что эта сумма содержит все числа, которые делятся на 2 до 2*n. Эти числа являются первыми n числами, которые делятся на 2.

Следовательно, сумма первых n чисел, которые делятся на 2, равна 2 * sum(n). Мы можем обобщить это, чтобы написать функцию, которая возвращает сумму первых n чисел, которые делятся на m:

int sum_div_m( int n, int m) {
    return sum(n) * m;
}

Сначала я хочу воспроизвести ваш первоначальный пример "до 60 суммы это 870 ". Для этого мы считаем, что

• 60/3 == 20 -> есть 20 чисел, кратных 3, и мы получаем их сумму от sum_div_m(20,3)
• 60/5 == 12 -> есть 12 чисел, делимых на 5, и мы получаем их сумму от sum_div_m(12,5)
• , мы не можем просто добавить два вышеупомянутых результата, потому что тогда мы будем считать некоторые числа двойными. Эти числа делятся на 3 и 5, ie делятся на 15
• 60/15 == 4 -> есть 4 числа, делимые на 3 и 5, и мы получить их сумму от sum_div_m(4,15).

Если сложить ее вместе, сумма всех чисел, кратных 3 или 5 до 60, составит

int x = sum_div_m( 20,3) + sum_div_m( 12,5) - sum_div_m( 4,15);

Наконец, вернемся к вашему актуальному вопросу:

Но что, если я хочу только первые 15 кратных?

Выше мы видели, что есть

n == x/3 + x/5 - x/15

числа, которые делятся на 3 или 5 в диапазоне 0...x. Все деления используют целочисленную арифметику. У нас уже был пример 60 с 20+12-4 == 28 делимыми числами. Другой пример - x=10, где есть n = 3 + 2 - 0 = 5 чисел, кратных 3 или 5 (3,5,6,9,10). Мы должны быть немного осторожнее с целочисленной арифметикой, но ничего страшного:

    15*n == 5*x + 3*x - x
->  15*n == 7*x
->  x == 15*n/7 

Быстрый тест: 15*28/7 == 60, выглядит правильно.

Собираем все вместе сумму первых n числа, делимые на 3 или 5, равны

int sum_div_3_5(int n) {
    int x = (15*n)/7;
    return sum_div_m(x/3, 3) + sum_div_m(x/5, 5) - sum_div_m(x/15, 15);
}

Чтобы проверить, что это правильно, мы можем снова попробовать sum_div_3_5(28), чтобы увидеть, что он возвращает 870 (потому что есть 28 числа делятся на 3 или 5 до 60, и это был первоначальный пример).

PS Оказалось, что вопрос на самом деле касается только математики. Хотя это не большой сюрприз. Если вы хотите написать эффективный код, вы должны прежде всего позаботиться об использовании правильного алгоритма. Оптимизации на основе данного алгоритма часто менее эффективны, чем выбор лучшего алгоритма. После того, как вы выбрали алгоритм, часто он не окупается, пытаясь быть «умным», потому что компиляторы гораздо лучше оптимизируют. Например, этот код:

int main(){
    int x = 0; 
    int n = 60;
    for (int i=0; i <= n; ++i) x += i;
    return x;
}

будет оптимизирован большинством компиляторов до простого return 1830;, когда оптимизация включена, потому что компиляторы знают, как добавить все числа от 1 до n. Смотри здесь .

Answer 2

Вы можете сделать это во время компиляции рекурсивно, используя шаблоны классов / мета-функции, если ваше значение известно во время компиляции. Таким образом, не будет никаких затрат времени выполнения.

Пример:

template<int n>
struct Sum{
    static const int value = n + Sum<n-1>::value;
};

template<>
struct Sum<0>{
    static constexpr int value = 0;
};

int main()
{
    constexpr auto x = Sum<100>::value;
    // x is known (5050) in compile time
    return 0;
}