views:

1354

answers:

9

I did this problem [Project Euler problem 5], but very bad manner of programming, see the code in c++,

#include<iostream>
using namespace std;
// to find lowest divisble number till 20

int main()
{
int num = 20, flag = 0;

while(flag == 0)
{
    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)       

    {
        flag =  1;
        cout<< " lowest divisible number upto 20 is  "<< num<<endl;
    }

    num++;
}

}

i was solving this in c++ and stuck in a loop, how would one solve this step......

  • consider num = 20 and divide it by numbers from 1 to 20
  • check whether all remainders are zero,
  • if yes, quit and show output num
  • or else num++

i din't know how to use control structures, so did this step

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) `

how to code this in proper manner?

answer for this problem is:

abhilash@abhilash:~$ ./a.out 
 lowest divisible number upto 20 is  232792560
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:

2
3
5
7 
11
13
17
19

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
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
"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
This is wrong, you have not checked that the result was divisible by 16.
Pascal Cuoq
+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
+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
I knew it had something to do with prime numbers, but I completely missed the boat. :(
knight666
+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
+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.
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
+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
yes when i tried this earlier, each time (num % divisor ==0) i forgot to use break, now its simple. Thanks
abhilashm86
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
try this code for numbers from 1 to 1000
ralu
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
@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
@Pascal: Oh no! What have I done?! :-)
James McNellis
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
Am I missing something? This is only helpful if you already know the answer.
Iceman
+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
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