Step by Step solution about How to resolve the algorithm Sum multiples of 3 and 5 step by step in the C programming language

The C code is a program that calculates the sum of all multiples of 3 or 5 below a given integer. The program takes an optional command line argument which specifies the upper limit of the calculation. If no argument is given, a default limit of 1000 is used.

The first version of the program, sum35, computes the sum in a straightforward manner using a loop to iterate over all the numbers up to the given limit and checking if each number is a multiple of 3 or 5. The sum of all such numbers is returned as the result.

The second version of the program, sum_multiples, uses a more efficient technique to compute the sum. It calculates the sum of all multiples of the given factor up to the given limit using the formula:

sum of multiples of f up to n = (n/f) * (f + n/f) / 2

This formula is derived from the fact that the sum of an arithmetic series is equal to the product of the first and last terms divided by 2.

To compute the sum of all multiples of 3 or 5 up to the given limit, the program uses the sum_multiples function twice, once for the factor 3 and once for the factor 5. It then subtracts the sum of all multiples of 15 (which are counted twice in the previous two sums) to get the final result.

The overall complexity of the sum_multiples function is O(1), as it only performs a constant number of operations regardless of the size of the input. This makes it much more efficient than the sum35 function, which has a complexity of O(n), where n is the given limit.

Here is a breakdown of the code:

• The first section of the code defines the sum35 function, which takes an unsigned long long integer as an argument and returns the sum of all multiples of 3 or 5 below that integer.
• The main function takes an optional command line argument, which specifies the upper limit of the calculation. If no argument is given, a default limit of 1000 is used.
• The main function calls the sum35 function with the given limit and prints the result.

The second section of the code defines the sum_multiples function, which takes three arguments: a pointer to an mpz_t variable to store the result, a pointer to an mpz_t variable containing the limit, and an unsigned integer specifying the factor.

• The sum_multiples function calculates the sum of all multiples of the given factor up to the given limit using the formula:

sum of multiples of f up to n = (n/f) * (f + n/f) / 2

• The main function takes an optional command line argument, which specifies the upper limit of the calculation. If no argument is given, a default limit of 1000000000000000000000 is used.
• The main function calls the sum_multiples function three times, once for each of the factors 3, 5, and 15.
• The main function subtracts the sum of all multiples of 15 from the sum of all multiples of 3 and 5 to get the final result.
• The main function prints the result to the standard output stream.

The overall complexity of the sum_multiples function is O(1), as it only performs a constant number of operations regardless of the size of the input. This makes it much more efficient than the sum35 function, which has a complexity of O(n), where n is the given limit.

#include <stdio.h>
#include <stdlib.h>

unsigned long long sum35(unsigned long long limit)
{
    unsigned long long sum = 0;
    for (unsigned long long i = 0; i < limit; i++)
        if (!(i % 3) || !(i % 5))
            sum += i;
    return sum;
}

int main(int argc, char **argv)
{
    unsigned long long limit;

    if (argc == 2)
        limit = strtoull(argv[1], NULL, 10);
    else
        limit = 1000;

    printf("%lld\n", sum35(limit));
    return 0;
}


#include <stdio.h>
#include <gmp.h>

void sum_multiples(mpz_t result, const mpz_t limit, const unsigned f)
{
    mpz_t m;
    mpz_init(m);
    mpz_sub_ui(m, limit, 1);
    mpz_fdiv_q_ui(m, m, f);

    mpz_init_set(result, m);
    mpz_add_ui(result, result, 1);
    mpz_mul(result, result, m);
    mpz_mul_ui(result, result, f);
    mpz_fdiv_q_2exp(result, result, 1);

    mpz_clear(m);
}

int main(int argc, char **argv)
{
    mpf_t temp;
    mpz_t limit;

    if (argc == 2)
    {
        mpf_init_set_str(temp, argv[1], 10);
        mpz_init(limit);
        mpz_set_f(limit, temp);
        mpf_clear(temp);
    }
    else
        mpz_init_set_str(limit, "1000000000000000000000", 10);

    mpz_t temp_sum;
    mpz_t sum35;
    
    mpz_init(temp_sum);
    sum_multiples(temp_sum, limit, 3);
    mpz_init_set(sum35, temp_sum);
    sum_multiples(temp_sum, limit, 5);
    mpz_add(sum35, sum35, temp_sum);
    sum_multiples(temp_sum, limit, 15);
    mpz_sub(sum35, sum35, temp_sum);

    mpz_out_str(stdout, 10, sum35);
    puts("");

    mpz_clear(temp_sum);
    mpz_clear(sum35);
    mpz_clear(limit);
    return 0;
}