ansaurus

Question

Smallest number that is evenly divisible by all of the numbers from 1 to 20?

Answer 1

A:

Given the maximum n, you want to return the smallest number that is dividable by 1 through 20.

Let's look at the set of 1 to 20. First off, it contains a number of prime numbers, namely:

So, because it's has to be dividable by 19, you can only check multiples of 19, because 19 is a prime number. After that, you check if it can be divided by the one below that, etc. If the number can be divided by all the prime numbers successfully, it can be divided by the numbers 1 through 20.

float primenumbers[] = { 19, 17, 13, 11, 7, 5, 3, 2; };

float num = 20;

while (1)
{
   bool dividable = true;
   for (int i = 0; i < 8; i++)
   {
      if (num % primenumbers[i] != 0)
      {
         dividable = false;
         break;
      }
   }

   if (dividable) { break; }
   num += 1;
}

std::cout << "The smallest number dividable by 1 through 20 is " << num << std::endl;

knight666 2010-01-24 12:55:21

this is buggy(can't use % on floats), and doesn't return the number 232792560. The return for your method is 9699690 is not divided by 18.

Pentium10 2010-01-24 13:01:54

"because it's has to be dividable by 19, you can only check multiples of 19, because 19 is a prime number" -> not sure what that has to do with 19 being a prime?

Johannes Schaub - litb 2010-01-24 13:04:39

This is wrong, you have not checked that the result was divisible by 16.

Pascal Cuoq 2010-01-24 13:06:34

Answer 2

+3 A:

See http://en.wikipedia.org/wiki/Greatest_common_divisor Given two numbers a and b you can compute gcd(a, b) and the smallest number divisible by both is a * b / gcd(a, b). The obvious thing then to do is to keep a sort of running total of this and add in the numbers you care about one by one: you have an answer so far A and you add in the next number X_i to consider by putting

A' = A * X_i / (gcd(A, X_i))

You can see that this actually works by considering what you get if you factorise everything and write them out as products of primes. This should pretty much allow you to work out the answer by hand.

mcdowella 2010-01-24 12:58:13

Answer 3

+10 A:

Factor all the integers from 1 to 20 into their prime factorizations. For example, factor 18 as 18 = 3^2 * 2. Now, for each prime number p that appears in the prime factorization of some integer in the range 1 to 20, find the maximum exponent that it has among all those prime factorizations. For example, the prime 3 will have exponent 2 because it appears in the factorization of 18 as 3^2 and if it appeared in any prime factorization with an exponent of 3 (i.e., 3^3), that number would have to be at least as large as 3^3 = 27 which it outside of the range 1 to 20. Now collect all of these primes with their corresponding exponent and you have the answer.

So, as example, let's find the smallest number evenly divisible by all the numbers from 1 to 4.

2 = 2^1
3 = 3^1
4 = 2^2

The primes that appear are 2 and 3. We note that the maximum exponent of 2 is 2 and the maximum exponent of 3 is 1. Thus, the smallest number that is evenly divisible by all the numbers from 1 to 4 is 2^2 * 3 = 12.

Here's a relatively straightforward implementation.

#include <iostream>
#include <vector>

std::vector<int> GetPrimes(int);
std::vector<int> Factor(int, const std::vector<int> &);

int main() {
    int n;
    std::cout << "Enter an integer: ";
    std::cin >> n;
    std::vector<int> primes = GetPrimes(n);
    std::vector<int> exponents(primes.size(), 0);

    for(int i = 2; i <= n; i++) {
        std::vector<int> factors = Factor(i, primes);
        for(int i = 0; i < exponents.size(); i++) {
            if(factors[i] > exponents[i]) exponents[i] = factors[i];
        }
    }

    int p = 1;
    for(int i = 0; i < primes.size(); i++) {
            for(int j = 0; j < exponents[i]; j++) {
            p *= primes[i];
        }
    }

    std::cout << "Answer: " << p << std::endl;
}

std::vector<int> GetPrimes(int max) {
    bool *isPrime = new bool[max + 1];
    for(int i = 0; i <= max; i++) {
        isPrime[i] = true;
    }
    isPrime[0] = isPrime[1] = false;
    int p = 2;
    while(p <= max) {
        if(isPrime[p]) {
            for(int j = 2; p * j <= max; j++) {
                isPrime[p * j] = false;
            }
        }
        p++;
    }

    std::vector<int> primes;

    for(int i = 0; i <= max; i++) {
        if(isPrime[i]) primes.push_back(i);
    }

    delete []isPrime;
    return primes;
}

std::vector<int> Factor(int n, const std::vector<int> &primes) {
    std::vector<int> exponents(primes.size(), 0);
    while(n > 1) {
        for(int i = 0; i < primes.size(); i++) {
        if(n % primes[i] == 0) { 
        exponents[i]++;
            n /= primes[i];
        break;
        }
            }
    }
    return exponents;
}

Sample output:

Enter an integer: 20
Answer: 232792560

Jason 2010-01-24 12:58:49

I knew it had something to do with prime numbers, but I completely missed the boat. :(

knight666 2010-01-24 13:12:05

Answer 4

+6 A:

The smallest number that is divisible by two numbers is the LCM of those two numbers. Actually, the smallest number divisible by a set of N numbers x1..xN is the LCM of those numbers. It is easy to compute the LCM of two numbers (see the wikipedia article), and you can extend to N numbers by exploiting the fact that

LCM(x0,x1,x2) = LCM(x0,LCM(x1,x2))

Note: Beware of overflows.

Code (in Python):

def gcd(a,b):
    return gcd(b,a%b) if b else a

def lcm(a,b):
    return a//gcd(a,b)*b

print reduce(lcm,range(2,21))

MAK 2010-01-24 12:59:55

Answer 5

+2 A:

Hint:

instead of incrementing num by 1 at each step you could increment it by 20 (will work alot faster). Of course there may be other improvements too, ill think about it later if i have time. Hope i helped you a little bit.

George B. 2010-01-24 13:00:05

Nice non-number-theoretical approach. A generalisation is to first compute the gcd of 19 and 20 (by brute force but incrementing by 20 as you suggest). When that number is found (call it X), find the gcd Y of that number with 18, incrementing by X each time, because the solution is necessarily a multiple of X. When Y is found ...

Pascal Cuoq 2010-01-24 13:05:19

Answer 6

+8 A:

There is a faster way to answer the problem, using number theory. Other answers contain indications how to do this. This answer is only about a better way to write the if condition in your original code.

If you only want to replace the long condition, you can express it more nicely in a for loop:

 if ((num%2) == 0 && (num%3) == 0 && (num%4) == 0    && (num%5) == 0 && (num%6) == 0 
&& (num%7) == 0 && (num%8) == 0 && (num%9) == 0 && (num%10) == 0 && (num%11) == 0 && (num%12) ==0   
&& (num%13) == 0 && (num%14) == 0 && (num%15) == 0 && (num%16) == 0 && (num%17) == 0 && (num%18)==0
&& (num%19) == 0    && (num%20) == 0)     
{ ... }

becomes:

{
  int divisor; 
  for (divisor=2; divisor<=20; divisor++)
    if (num%divisor != 0)
      break;
  if (divisor != 21)
  { ...}
}

The style is not great but I think this is what you were looking for.

Pascal Cuoq 2010-01-24 13:11:35

yes when i tried this earlier, each time (num % divisor ==0) i forgot to use break, now its simple. Thanks

abhilashm86 2010-01-24 13:15:25

Note that I got it wrong the first time. The `break` is to exit the loop on `divisor` when one of the numbers in 2..20 does not divide `num`. The `if (divisor!=21)` is to check if the loop was exited with such a `break;` or normally (because all numbers 2..20 divided `num`).

Pascal Cuoq 2010-01-24 13:34:38

try this code for numbers from 1 to 1000

ralu 2010-01-24 17:26:46

I think you mean `int divisor; for (divisor=2; divisor<=20; divisor++)`; if you place the declaration of `divisor` inside of the `for` statement, it won't be in scope when you test it when the loop ends.

James McNellis 2010-01-25 21:03:48

@James Darn, you're right. The one feature introduced in C++ that I find useful, and I misuse it. That's it, I'm sticking to C from now on.

Pascal Cuoq 2010-01-25 23:11:16

@Pascal: Oh no! What have I done?! :-)

James McNellis 2010-01-25 23:39:14

Answer 7

A:

This can help you http://www.mathwarehouse.com/arithmetic/numbers/prime-number/prime-factorization.php?number=232792560

The prime factorization of 232,792,560

2^4 • 3^2 • 5 • 7 • 11 • 13 • 17 • 19

Pentium10 2010-01-24 13:12:02

Am I missing something? This is only helpful if you already know the answer.

Iceman 2010-01-25 21:23:47

Answer 8

+1 A:

The number in question is the least common multiple of the numbers 1 through 20.

Because I'm lazy, let ** represent exponentiation. Let kapow(x,y) represent the integer part of the log to the base x of y. (For example, kapow(2,8) = 3, kapow(2,9) = 3, kapow(3,9) = 2.

The primes less than or equal to 20 are 2, 3, 5, 7, 11, 13, and 17. The LCM is,

Because sqrt(20) < 5, we know that kapow(i,20) for i >= 5 is 1. By inspection, the LCM is

LCM = 2**kapow(2,20) * 3**kapow(3,20) * 5 * 7 * 11 * 13 * 17 * 19

which is

LCM = 2**4 * 3**2 * 5 * 7 * 11 * 13 * 17 * 19

or

LCM = 16 * 9 * 5 * 7 * 11 * 13 * 17 * 19

John R. Strohm 2010-01-25 23:33:49

Answer 9

A:

Ruby Cheat:

require 'rational'

def lcmFinder(a = 1, b=2)
  if b <=20
    lcm = a.lcm b
    lcmFinder(lcm, b+1)
  end
  puts a
end


lcmFinder()

zengr 2010-09-16 06:49:38

ansaurus

tags:

views:

answers:

Smallest number that is evenly divisible by all of the numbers from 1 to 20?

related questions