CODEWITHSUNDEEP
c++algorithmif-statement
Abhilash Muthuraj
Abhilash Muthuraj

Reputation: 2028

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

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......

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

Upvotes: 8

Views: 32931

Answers (14)

Sathish Kumar Krushaa
Sathish Kumar Krushaa

Reputation: 11

Code in JavaScript:

var i=1,j=1;
    
for (i = 1; ; i++) {
    for (j = 1; j <= 20; j++) {
    
        if (i % j != 0) {
            break;
        }
        if (i % j == 0 && j == 20) {
            console.log('printval' + i)
            break;
        }
    }
}

Upvotes: 1

Manas_Yeole
Manas_Yeole

Reputation: 3

This is why you would benefit from writing a function like this:

long long getSmallestDivNum(long long n)
{
    long long ans = 1;
    if( n == 0)
    {
        return 0;
    }
    for (long long i = 1; i <= n; i++) 
        ans = (ans * i)/(__gcd(ans, i)); 
    return ans; 
}

Upvotes: 0

Brian Ogden
Brian Ogden

Reputation: 19212

Here is a C# version of @MAK's answer, there might be List reduce method in C#, I found something online but no quick examples so I just used a for loop in place of Python's reduce: 

static void Main(string[] args)
    {
        const int min = 2;
        const int max = 20;
        var accum = min;

        for (var i = min; i <= max; i++)
        {
            accum = lcm(accum, i);
        }

        Console.WriteLine(accum);
        Console.ReadLine();
    }

    private static int gcd(int a, int b)
    {
        return b == 0 ? a : gcd(b, a % b);
    }

    private static int lcm(int a, int b)
    {
        return a/gcd(a, b)*b;
    }

Upvotes: 1

vector_L
vector_L

Reputation: 11

#include<vector>
using std::vector;
unsigned int Pow(unsigned int base, unsigned int index);

unsigned int minDiv(unsigned int n)
{
     vector<unsigned int> index(n,0);
     for(unsigned int i = 2; i <= n; ++i)
     {
         unsigned int test = i;
         for(unsigned int j = 2; j <= i; ++j)
         {
             unsigned int tempNum = 0;
             while( test%j == 0)
             {
                 test /= j;
                 tempNum++;
             }
             if(index[j-1] < tempNum)
                 index[j-1] = tempNum;
         }
     }
     unsigned int res =1;
     for(unsigned int i = 2; i <= n; ++i)
     {
         res *= Pow( i, index[i-1]);
     }
     return res;
 }

unsigned int Pow(unsigned int base, unsigned int index)
{
    if(base == 0)
        return 0;
    if(index == 0)
        return 1;
    unsigned int res = 1;
    while(index)
    {
        res *= base;
        index--;
    }
    return res;
}

The vector is used for storing the factors of the smallest number.

Upvotes: 0

MAK
MAK

Reputation: 26586

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

Upvotes: 19

Indrajith Indraprastham
Indrajith Indraprastham

Reputation: 1

this is written in c

#include<stdio.h>
#include<conio.h>
void main()
{

int a,b,flag=0;

for(a=1; ; a++)
{
    for(b=1; b<=20; b++)
    {
        if (a%b==0)
            {
                flag++;
            }

    }
    if (flag==20)
        {
            printf("The least num divisible by 1 to 20 is = %d",a);
            break;
        }
        flag=0;
}


getch();

}

Upvotes: 0

zengr
zengr

Reputation: 38899

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

Upvotes: 0

John R. Strohm
John R. Strohm

Reputation: 7667

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 = 2kapow(2,20) * 3kapow(3,20) * 5 * 7 * 11 * 13 * 17 * 19

which is

LCM = 24 * 32 * 5 * 7 * 11 * 13 * 17 * 19

or

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

Upvotes: 1

Pascal Cuoq
Pascal Cuoq

Reputation: 80276

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.

Upvotes: 10

jason
jason

Reputation: 241611

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

Upvotes: 16

Pentium10
Pentium10

Reputation: 207838

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

Upvotes: 0

George
George

Reputation: 3845

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.

Upvotes: 2

mcdowella
mcdowella

Reputation: 19601

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.

Upvotes: 4

knight666
knight666

Reputation: 1619

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;

Upvotes: -3

Related Questions