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

Question

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

Code for this:

#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 also does not work. Why?

Answer 1

I would calculate it in a completely different way: LCM of {1, ..., n} is the product of all primes p [i] <= n, each in the force floor (log (n) / log (Pi])). This product is divided by all numbers up to n, and this is the smallest such number. Your main problem is to compute a prime table.

Answer 2

Your current solution is incorrect, as mentioned in the comments.

One way to solve this is to realize that the LCM of these numbers is just the product of all the "greatest" degrees of various prime numbers less than or equal to n . That is, find each prime p less than or equal to n , then find the greatest degree of each of these primes, such that it is even less than or equal to n , and multiply them together. For a given p indicated power can be expressed in pseudo-code as:

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

Here's the implementation in Golang, which 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, here is the full code from this playground:

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

Answer 3

I'm going to suggest something less dynamic, but that will dramatically increase your speed. Set up the factorial table (possibly an array) and save the precomputed factorial integer views. So this is a simple operation O (1) compared to O (n). This is a look-up table, but you can also calculate it in advance: http://www.tsm-resources.com/alists/fact.html This is normal because these values ​​will never change. If we are talking about speed optimization, then why not save the values ​​that we know, and not calculate them every time?

If you, however, do not agree with saving these calculations in advance, I suggest looking at the optimized algorithms and making your way from there:

Here are two great resources for faster factorial calculation algorithms:

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

Answer 4

It is very simple, but it seems that it works fast enough. Probably the idea of ​​Amit Kumar Gupta is faster. Stack overflow around n = 9500 on my machine, but this could be fixed by saving the memoizing function and creating a note from small numbers to large numbers. I did not accept the module, but this fix is ​​easy, especially if the module is simple. 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)); } }