UVAOJ - 10680 - LCM

Problem Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1621


Idea: The idea is simple if we want to calculate the LCM for the numbers of 

1,2,3,⋯,n we first list all the prime factors between [1,n]. For each factor in that list we need the maximum exponent such that px≤n. In other words, let's say that n=20 we want to know the highest power of 2 in the LCM(1,2,⋯,20) we can try the following:

21≤20 (true)

22≤20 (true)

23≤20 (true)

24≤20 (true)

25≤20 (false)

So the largest power of 2 in the LCM(1,2,⋯,20) is 24.

We repeat this process for the other prime factor in the range [1,n]. After that for each prime factor we calculate the answer mod 10. To avoid getting 0's at the end we subtract the cnt2−cnt5, because between 1,2,3,⋯,n always there is going to be more factors of two than factors of five, this subtraction is always going to be greater than 0.

Code First Then See Solution
Code: 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

bool a[1000397];
vector <int> v;
int mx=1000356;

void sieve()
{
    memset(a,true,sizeof(a));
    a[0]=a[1]=false;
    v.push_back(2);
    for(int i=3;i<=sqrt(mx);i+=2)
    {
        if(a[i]==true)
            for(int j=i*i;j<=mx;j+=i)
              a[j]=false;
    }
    for(int i=3;i<=mx;i+=2)
    {
        if(a[i]==true)
         v.push_back(i);
    }
    swap(v[1],v[2]);
}

int main()
{
    ll n;
    sieve();
    while(cin>>n)
    {
        if(n==0)
            break;
        ll sum=1;
        ll cnt2=0,cnt5=0;
        for(ll i=2;i<=n;i*=2)
          cnt2++;
        for(ll i=5;i<=n;i*=5)
          cnt5++;
        for(ll i=0;i<cnt2-cnt5;i++)
        {
            sum*=2;
            sum%=10;
        }
        for(int i=2;i<v.size()&&v[i]<=n;i++)
        {
            for(ll j=v[i];j<=n;j*=v[i])
            {
                sum*=v[i];
                sum%=10;
            }
        }
         cout<<sum<<endl;
    }
    return 0;

}