2
\$\begingroup\$

This is a problem from Project Euler and on Hackerrank (here)-

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible (divisible with no remainder) by all of the numbers from 1 to N?

Input Format First line contains that denotes the number of test cases. This is followed by lines, each containing an integer, .

Output Format Print the required answer for each test case.

Constraints

1 <= T <= 10
1 <= N <= 40

Sample Input

2
3
10

Sample Output

6
2520

Here is the code I wrote. My approach was to first create a table of prime factors and use them to generate a number that is divisible by all numbers below N. Is there a better approach? Is there something that I am doing here that is very sub-optimal?

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    int T,N,i,j,k,q,M[40],p;
    scanf("%d",&T);
    M[0]=1;
    M[1]=2;
    M[2]=3;
    for (i=3;i<40;i++){
        q=i+1;
        for (j=1;j<i;j++){
            if (q%M[j]==0){
                q/=M[j];
            }
        }
        M[i]=q;
    }
    for (i=0;i<T;i++){
        scanf("%d",&N);
        p=1;
        for (j=0;j<N;j++){
            p*=M[j];
        }
        printf("%d\n",p);
    }
    return 0;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Please add a language tag. \$\endgroup\$ – Heslacher Jul 12 '16 at 5:46
  • 1
    \$\begingroup\$ I probably said this to other posts, but I really believe it is helping you and us when trying to read your code. Make sure you give variables meaningful names. For now I wouldn't event know what is what as everything is ambiguously defined using one letter. If you want answers you should make your code as readable as possible. Good luck! \$\endgroup\$ – Mihai-Daniel Virna Jul 12 '16 at 7:15
  • \$\begingroup\$ Unless I made an error, the results are wrong for N >= 23. \$\endgroup\$ – Martin R Jul 12 '16 at 8:13
  • \$\begingroup\$ Oh... It passed all the test cases :-/ Lucky me ;-) \$\endgroup\$ – Lord Loh. Jul 12 '16 at 8:31
  • 3
    \$\begingroup\$ @LordLoh. Please do not update the code in your question after receiving answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. Particularly the part about posting a new question linking back to this one. \$\endgroup\$ – mdfst13 Jul 12 '16 at 22:03
3
\$\begingroup\$

Truly choose your language

Although a C compiler won't accept the program as a whole (due to the using directive and choice of headers) the actual code here is all really C. I'd make up my mind and either write C in a way that's acceptable to a C compiler, or else write C++ that makes good use of the language. The combination you've used is (IMO) pretty much a pit of despair.

For the remainder of this review, I'm going to go with the tag, and assume you really wanted to write good C++.

Avoid C's variadic I/O functions

Although some parts of the C library are fine, C's variadic I/O functions such as scanf and printf are quite problematic in one respect: they provide essentially no type safety. As shown by dozens (probably hundreds, if you looked carefully) of questions on Stack Overflow, mismatches between the formatting argument and the other arguments frequently cause problems. There are a few cases where you're reading or writing highly formatted data that it might be worth at least considering using these functions anyway, but the I/O format specified here doesn't provide any such justification.

Use the right types

In C++, there's rarely much reason to use a built in array such as your M. You're usually better off with a std::array or std::vector instead.

Likewise, the values we need for inputs up to 40 can exceed the range of a 32-bit number. We probably want to use unsigned long long (or something on the same general order) to support the specified range.

Names

As @NullException hinted at in the comments, most of the variable names in this code border on meaningless. I consider it perfectly acceptable to use a name like i for a subscript in a loop, but for longer-lived things like your M, a more meaningful name would be extremely helpful.

Consider a more recognizable algorithm

When you get down to it, what we're dealing with here is computing the least common multiple (LCM) of some numbers. There's a well-known method of computing the LCM of numbers: LCM(a, b) = a * b / gcd(a, b). This can be extended to three or more numbers quite easily:

LCM(a, b, c) = 
    L = lcm(a, b); 
    result = L * c / gcd(L,c)

Since this defines the LCM of three numbers in terms of the LCM of two numbers, we can extend it indefinitely.

Define functions where suitable

In this case, our definition of LCM depends on the GCD. Computing the GCD of two inputs is a well-defined operation that should probably be defined as a function.

Consider a greedy algorithm

In this case, we have only 40 possible inputs. We also have an algorithm for computing LCMs, where each result depends on the previous result. It's probably easiest to start by computing the LCM for every possible input from 1 to 40, then read the actual inputs, and just print out the result for each.

Result

Putting those suggestions together, we might get code something like this:

#include <map>
#include <vector>
#include <iostream>

template <class T>
T GCD(T u, T v) {
    while (v != 0) {
        T r = u % v;
        u = v;
        v = r;
    }
    return u;
}

int main() {
    using T = unsigned long long;

    std::vector<T> LCMs{ 1 }; // The LCM of 1 is 1

    // Compute succeeding LCMs based on existing one(s)
    for (T i = 2; i < 40; i++) {
        auto prev = LCMs.back();
        LCMs.push_back(prev * i / GCD(prev, i));
    }

    int test_count;
    std::cin >> test_count;

    for (int n = 0; n < test_count; n++) {
        int input;
        std::cin >> input;

        std::cout << LCMs[input-1] << "\n";
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ does it really make sense to template the integer type. It must be an integer, it cant be 32-bit. So it has to be long long. BTW - awesome example of templating tho. \$\endgroup\$ – pm100 Jul 12 '16 at 22:37
  • \$\begingroup\$ @pm100: at least IMO, yes, the template makes sense. Even if we need long long for this application, there are lots of cases where you want to compute a GCD on a smaller type, and no particularly good reason to rewrite the code to suit. For this application, it could also make perfect sense to use some arbitrary precision integer type instead. \$\endgroup\$ – Jerry Coffin Jul 13 '16 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.