Project Euler #5

[Edwards]

This question was incredibly easy to "program" though I feel like my way was the most inefficient way of doing it and was curious as to how I should have went about it else wise. Any help understanding how to simplify this would be much appreciated.

int main()
{
    for(int n = 1; n!=0; n++){
        if (n%1==0 && n%2==0 && n%3==0 && n%4==0 && n%5==0 && n%6==0 && n%7==0 && n%8==0 && n%9==0 && n%10==0 && n%11==0 && n%12==0 && n%13==0 && n%14==0 && n%15==0 && n%16==0 && n%17==0 && n%18==0 && n%19==0 && n%20==0){
            cout << n << endl;
            return 0;
        }
    }
}

I feel like I don't need 20 different &&'s for this to be logical lol.

[cire]

http://codereview.stackexchange.com/questions/13086/problem-5-on-project-euler

[Edwards]

lord...guess this is much more math intensive than I first imagined...not sure if I'm even in my realm with all these problems lol.

[keskiverto]

You could at least learn how that lenghty condition was compressed into a loop.

[giblit]

You don't need to check all the numbers from 1-20 anyways..Also why are you checking if it is divisible by 1 sorry but that is just funny :P


The numbers you will need to check:
-primes
-anything else missing

primes: 2 3 5 7 11 13 17 19
some of these primes we won't need however since they are factors of larger numbers.


Lets look at the numbers from 20 - 1 instead of 1 - 20

20 = 20 x 1, or 2 x 10, or 4 x 5 (so we wont need any of those numbers) -missing 1, 2, 4, 5, 10, 20
19 = 19 x 1 - missing 19
18 = 18 x 1 or 9 x 2 or 6 x 3 - missing 3, 6, 9, 18
17 = 17 x 1 - missing 17
16 = 16 x 1 or 8 x 2 - missing 8, 16
15 = 15 x 1, 5 x 3 - missing 15
14 = 14 x 1, 7 x 2 - missing 7, 14
13 = 13 x 1 - missing 13
12 = 12 x 1, 6 x 2, 4 x 3 - missing 12
11 = 11x1 - missing 11
20-11 = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

so we don't need anymore.

Also the number is within the range of: [2520, 670442572800]

Another approach is the complete prime factoring.

20 = 2² x 5
19 = 19
18 = 2 x 3²
17 = 17
16 = 2⁴
15 = 3 x 5
14 = 2 x 7
13 = 13
12 = 2² x 3
11 = 11
you can get the rest of the factors but they will be less than the above as I mentioned earlier since they already have all the primes from 2->19

So it must be divisible by <SPOILER>
















2⁴ x 3² x 5 x 7 x 11 x 13 x 17 x 19 = 232792560</SPOILER>