Найти сумму всех кратных 3 или 5 ниже 1000

Question

Если мы перечислим все натуральные числа ниже 10, кратные 3 или 5, мы получим 3, 5, 6 и 9. Сумма этих кратных равна 23. У меня есть следующий код, но ответ не совпадает.

#include<stdio.h>
int main()
{
    long unsigned int i,sum=0;
    clrscr();
    for(i=0;i<=1000;i++)
    {
        if((i%5==0)||(i%3==0))
        {
            sum=sum+1;
        }
    }
    printf("%d\n",sum);
    getchar();
    return 0;
}

Answer 1

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

Существует простой способ получить сумму, кратную числу, меньшему, чем число.

Например, сумма, кратная 3 до 1000: 3 + 6 + 9 + ... + 999 Который может быть переписан как: 3 * (1 + 2 + 3 + ... + 333)

Существует простой способ суммирования всех чисел 1-N:

Sum(1,N) = N*(N+1)/2

Таким образом, функция выборки будет

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

Таким образом, теперь все кратные 3, меньшие 1000 (до 999 включительно), теперь уменьшены до:

3*unitSum((int)(999/3))

Вы можете сделать то же самое для кратных 5:

5*unitSum((int)(999/5))

Но есть одна оговорка! Оба этих числа кратны обоим, таким как 15, 30 и т. Д. Он считает их дважды, по одному на каждого. Таким образом, чтобы уравновесить это, вы вычитаете один раз.

15*unitSum((int)(999/15))

Итак, в целом, уравнение:

sum = 3*unitSum((int)(999/3)) + 5*unitSum((int)(999/5)) - 15*unitSum((int)(999/15))

Так что теперь вместо того, чтобы циклически проходить по большому набору чисел и делать сравнения, вы просто делаете простое умножение!

Answer 2

Две вещи:

• вы , включая 1000 в цикле, и
• вы добавляете единицу к сумме каждый раз, а несамо значение.

Измените цикл на

for(i=0;i<1000;i++)

И строку суммы на

sum=sum+i;

Answer 3

Возможно, вам следует сделать

sum += i // or sum = sum + i

вместо

sum = sum + 1

Кроме того, будьте осторожны при печати long unsigned int s с printf.Я предполагаю, что правильный спецификатор %lu.

Answer 4

Должно быть sum = sum + i вместо 1.

Answer 5

#include<stdio.h>
#include<time.h>
int main()
{
    int x,y,n;
    int sum=0;
    printf("enter the valeus of x,y and z\n");
    scanf("%d%d%d",&x,&y,&n);
    printf("entered   valeus of x=%d,y=%d and z=%d\n",x,y,n);
    sum=x*((n/x)*((n/x)+1)/2)+y*((n/y)*((n/y)+1)/2)-x*y*(n/(x*y))*((n/(x*y))+1)/2;
    printf("sum is %d\n",sum);
    return 0;
}
// give x,y and n  as 3 5 and 1000

Answer 6

Интересный факт разницы во времени между этими двумя методами ... Второй метод просто вычисляет только с необходимыми числами и не повторяет цикл.Пример: 3 * (1 + 2 + 3 + 4 ... 333) (потому что 3 * 333 = 999 и 999 <1000. </p>

   static void Main(string[] args)
    {
        Stopwatch sw = new Stopwatch();

        Calc calculator = new Calc();
        long target = 999999999;
        sw.Start();
        Console.WriteLine("Result: " +  (calculator.calcMultipleSumFast(3,target) + calculator.calcMultipleSumFast(5, target) - calculator.calcMultipleSumFast(15, target)));
        sw.Stop();
        Console.WriteLine("Runtime: " + sw.Elapsed);
        Console.WriteLine();
        sw.Start();
        Console.WriteLine("Result: " + (calculator.calcMultiplesSum(3, 5,1000000000)));
        sw.Stop();
        Console.WriteLine("Runtime: " + sw.Elapsed);

        Console.ReadKey();
    }

    public class Calc
{
    public long calcMultiplesSum(long n1, long n2, long rangeMax)
    {
        long sum = 0;
        for (long i = 0; i < rangeMax; i++)
        {
            if ((i % n1 == 0) || (i % n2 == 0))
            {
                sum = sum + i;
            }
        }
        return sum;
    }

    public long calcMultipleSumFast(long n, long rangeMax)
    {
        long p = rangeMax / n;

        return (n * (p * (p + 1))) / 2;
    }
}

Answer 7

Так же, как улучшение, вы можете вообще избежать цикла:

multiples of 3 below 1000 form an AP : 3k where k in [1, 333]
multiples of 5 below 1000 form an AP : 5k where k in [1, 199]

Если мы избегаем кратных как 3, так и 5: 15k, где k в [1, 66]

So the answer is : 333*(3+999)/2 + 199(5+995)/2 - 66*(15+990)/2 = 2331 68

Почему вы можете захотеть это сделать, оставлено на ваше усмотрение.

Answer 8

Вот строка с одним вкладышем, которая дает правильный ответ (233168):

reduce( lambda x,y: x+y, [ x for x in range(1000) if x/3.0 == int( x/3.0 ) or x/5.0 == int( x/5.0 ) ] )

Answer 9

Думайте декларативно - что вы хотите сделать, а не как вы хотите.

Говоря простым языком, он сводится к тому, что именно просит вас сделать проблема:

1. Найти все кратные 3 или 5 в определенном диапазоне (в данном случае от 1 до 1000)
2. Сложите их все (общая сумма)

В LINQ это выглядит так:

Enumerable.Range(1, 1000)
            .Where(x => (x % 3 == 0) || (x % 5 == 0))
            .Aggregate((accumulate, next) => accumulate += next);

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

Answer 10

int main(int argc, char** argv)
{
    unsigned int count = 0;
    for(int i = 1; i < 1001; ++i)
        if(!(i % 3) && !(i % 5))
            count += i;
    std::cout << i;
    return 0;
}