How to calculate Least common multiple of {1, 2, 3, .........., n}?

Question

How to find LCM of {1, 2, ..., n} where 0 < n < 10001 in fastest possible way. The one way is to calculate n! / gcd (1,2,.....,n) but this can be slow as number of testcases are t < 501 and the output should be LCM ( n! ) % 1000000007

Code for the same is:

#include<bits/stdc++.h>
using namespace std;
#define p 1000000007;
int fact[10001] = {1};
int gcd[10001] = {1};

int main()
{
    int i, j;
    for( i = 2;i < 10001; i++){
        fact[i] = ( i * fact[i-1]) % p;
    }
    for(i=2 ;i < 10001; i++){
        gcd[i] =__gcd( gcd[i-1], i );
    }

    int t;
    cin >> t;

    while( t-- ) {
        int n;
        cin >> n;
        int res = ( fact[n] / gcd[n] );
        cout << res << endl;
    }

    return 0;
}

But this code is not performing as well. Why?

Wergild

What does "this code is not performing as well" mean? – Martines

lcm(a, b) * gcd(a, b) = a * b does only hold for two numbers. It is not correct for more input parameters. lcm and gcd have a prime factor decomposition with the maximum and minimum exponents respectively, whereas the product sums them. And sum(e1, e2, ...) - min(e1, e2, ...) != max(e1, e2, ...). – Slovak

Check the OEIS for implementation options. – Slovak

gcd(1,2,...,n) = 1 always ... that can't be what you want. – Dunghill

Answer 1

I would calculate this in completely different way: the LCM of {1,...,n} is a product of all primes p[i]<=n, each in power floor(log(n)/log(p[i])). This product is divisible by all numbers up to n, and this is the least such number. Your main trouble is to calculate table of primes then.

Whippet

I suggest to use Erathosthen sieve to calculate table of primes up to 10001, should not take too long. – Whippet

Answer 2

Your current solution is not correct, as has been mentioned in the comments.

One way to solve this is to realize that the LCM of those numbers is just the product of all the "largest" powers of distinct primes less than or equal to n. That is, find each prime p less than or equal to n, then find the largest power of each of those primes such that it's still less than or equal to n, and multiply those together. For a given p, said power can be expressed in pseudocode as:

p ** math.Floor(math.Log(n) / math.Log(p))

Here's an implementation in Golang that returns immediately:

http://play.golang.org/p/8s4eE_CQ9Y

$ time go run lcm.go
5793339670287642968692270879166240098634860297998518825393138351148979300145773182308832598
<several lines later>
800000

real    0m0.225s
user    0m0.173s
sys     0m0.044s

For completeness, the full code from that playground link is pasted here:

package main

import (
    "fmt"
    "math"
    "math/big"
)

func main() {
    n := 10001

    primes := make([]int, 1, n)
    primes[0] = 2

SIEVE:
    for i := 3; i <= n; i++ {
        for _, p := range primes {
            if i%p == 0 {
                continue SIEVE
            }
        }
        primes = append(primes, i)
    }

    logN := math.Log(float64(n))
    lcm := big.NewInt(1)
    for _, p := range primes {
        floatP := float64(p)
        e := math.Floor(logN / math.Log(floatP))
        lcm.Mul(lcm, big.NewInt(int64(math.Pow(floatP, e))))
    }

    fmt.Println(lcm)
}

Karonkaross

Answer 3

I'm going to suggest something less dynamic, but it will increase your speed dramatically. Set up a factorial table (perhaps an array) and store pre-calculated factorial integer representations there. That way, it's a simple O(1) operation, versus O(n). Here's a reference table, but you may also precalculate those yourself: http://www.tsm-resources.com/alists/fact.html It's okay to do so, because those values will never change. If we're talking optimization for speed, then why not store the values we know, rather than calculate them each time?

If, however, you're opposed to storing these calculations beforehand, I suggest looking at optimized algorithms and work your way from there:

Here are two excellent resources for faster factorial calculation algorithms:

http://www.luschny.de/math/factorial/conclusions.html http://www.luschny.de/math/factorial/scala/FactorialScalaCsharp.htm

Martines

Answer 4

This is very simple but it seems to run fast enough. Probably Amit Kumar Gupta's idea is faster. Stack overflow around n = 9500 on my machine but that could be fixed by memoizing the function and building up the memo from small numbers to larger numbers. I didn't take the modulus but that fix is easy, particularly if the modulus is prime. Is it?

import java.math.BigInteger;

public class LCM {

  // compute f(n) = lcm(1,...n)
  public static BigInteger f(int n) {
    if (n == 1) return BigInteger.ONE;
    BigInteger prev = f(n-1);
    return prev.divide(prev.gcd(BigInteger.valueOf(n)))
      .multiply(BigInteger.valueOf(n));
  }

  public static void main(String[] args) {
    int n = Integer.parseInt(args[0]);
    System.out.println("f(" + n + ") = " + f(n));
  }
}

Dunghill