Given a range find the sum of number that is divisible by 3 or 5-CodePudding

The below code that works perfectly fine for smaller digits, But Time dilation for greater digits given me the suggestion

#include<stdio.h>
int main()
{
  int num;
  int sum=0;
  scanf("%d",&num);
  for(int i=1;i<=num;i  )
  {
    if(i%3==0 || i%5==0)
    sum  = i;
  }
  printf("%d",sum);
}

Need efficient code for this

Try to reduce the time take for the code.

CodePudding user response：

The answer can be computed with simple arithmetic without any iteration. Many Project Euler questions are intended to make you think about clever ways to find solutions without just using the raw power of computers to chug through calculations. (This was Project Euler question 1, except the Project Euler problem specifies the limit using less than instead of less than or equal to.)

Given positive integers N and F, the number of positive multiples of F that are less than or equal to N is ⌊N/F⌋. (⌊x⌋ is the greatest integer not greater than x.) For example, the number of multiples of 5 less than or equal to 999 is ⌊999/5⌋ = ⌊199.8⌋ = 199.

Let n be this number of multiples, ⌊N/F⌋.

The first multiple is F and the last multiple is n•F. For example, with 1000 and 5, the first multiple is 5 and the last multiple is 200•5 = 1000.

The multiples are evenly spaced, so the average of all of them equals the average of the first and the last, so it is (F nF)/2.

The total of the multiples equals their average multiplied by the number of them, so the total of the multiples of F less than N is n • (F n•F)/2.

Adding the sum of multiples of 3 and the sum of multiples of 5 includes the multiples of both 3 and 5 twice. We can correct for this by subtracting the sum of those numbers. Multiples of both 3 and 5 are multiples of 15.

Thus, we can compute the requested sum using simple arithmetic without any iteration:

#include <stdio.h>


static long SumOfMultiples(long N, long F)
{
    long NumberOfMultiples = N / F;
    long FirstMultiple = F;
    long LastMultiple = NumberOfMultiples * F;

    return NumberOfMultiples * (FirstMultiple   LastMultiple) / 2;
}


int main(void)
{
    long N = 1000;
    long Sum = SumOfMultiples(N, 3)   SumOfMultiples(N, 5) - SumOfMultiples(N, 3*5);

    printf("%ld\n", Sum);
}

As you do other Project Euler questions, you should look for similar ideas.