Deltron Z
Expert Cheater
![]() Reputation: 1
Joined: 14 Jun 2009
Posts: 164
|
 Posted: Mon Jun 14, 2010 2:55 pm Post subject: |
 |
|
Notice that the number must be divisible by all numbers 1 through 20, thus it must be divisble by 1, 2, 3, ..., 20.
If we take every number, 1 to 20, and find it's prime factors, we'll get:
2 - 2
3 - 3
4 - 2^2
5 - 5
6 - 2*3
7 - 7
8 - 2^3
9 - 3^2
10 - 2*5
11 - 11
12 - 2^2*3
13 - 13
14 - 2*7
15 - 3*5
16 - 2^4
17 - 17
18 - 2*3^2
19 - 19
20 - 2^2*5
Now, if we multipy 2*3*4*..*20 we actually get:
| Code: | 2 * 3 * 2^2 * 5 * 2*3 * 7 * 2^3 * 3^2 * 2*5 * 11 * 2^2*3 * 13 * 2*7 * 3*5 * 2^4 * 17 * 2*3^2 * 19 * 2^2*5
=>
2 * 3 * 2*2 * 5 * 2*3 * 7 * 2*2*2 * 3*3 * 2*5 * 11 * 2*2*3 * 13 * 2*7 * 3*5 * 2*2*2*2 * 17 * 2*3*3 * 19 * 2*2*5 |
And that's just wrong. (2432902008176640000)
Every number is produced by multipying prime factors, for example, 20 is 2*2*5.
So, we can simply create that number which divides all the numbers 1 to 20. to create such a number we can simply take 2*3*4*..*20 as in before, 2432902008176640000, and we've got such a number. but since we need the smallest one, we must first remove duplicates. if we take a look at the multipication of the prime factors of 1 to 20 we can easily see that 2*2 = 4 repeats itself, for 4, 8, 16 and 20 - which are all divisble by 20. so we'll take just 4, since 8 = 2*4 makes it repeat 2, 16 will repeat 4 and 20 will repeat 5.
So, first let's make a number which is divisible by all prime factors 1 to 20:
2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 = 9699690. this number is not divisible by 4, so multipy it by 2, since this number already contains 2 as a prime factor, and we only want 4. we can see it divides 5, 6 and 7 too, but not 8. since we multipied by 2, to get 8 = 2*2*2 we're missing another prime factor, 2, since we already have 4 = 2*2.
So we get 2 * 2 * 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 = 38798760.
Continue this process until 20, since it's not divisible by 9 and 16, we multipy it by 3 and 2 once again, since we already have the prime factor 3 of 9 = 3*3 and 2*2*2 of 16 = 2*2*2*2.
And so we get:
2 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 * 17 * 19.
So for conclusion, I'll make it short:
The smallest number divisible by all numbers, 1..n, in our case 1..20, is the multipication of all prime factors of 1..n with no common prime factors repeated, so since we want all 2, 4, 8 and 16 to divide that number we only need to multipy 16 which has all the prime factors of 2 (2), 4 (2*2) and 8 (2*2*2).
Basically, the math is simple, I guess it's just my explanation too bad so I had to make it long. 
An alternative can be a loop as you mentioned, at least optimize it. since the number must divide 20, you can make jumps by (at least) 20.
Another optimization could be checking only the numbers which are the highest power of a prime, p, under 20, so instead of checking 2, 4, 8 and 16 just check 16 (2^4).
Something like this: (can be optimized a lot more)
| Code: | int n = 20;
bool bFound = false;
while (bFound)
{
bFound = true;
for (int i = 20; i > 10; i--)
{
if (n % i != 0)
{
bFound = false;
break;
}
}
n += 20;
}
printf("%d\n", n); |
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Reputation: 65
