Anik_Akash

10680 - LCM

May 22nd, 2021 (edited)
99
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace    std;
  3. #define pb                push_back
  4. #define mx                1000006
  5.  
  6. typedef long long int       ll;
  7.  
  8. vector<int>prime;
  9. bool vis[mx];
  10. void sieve()
  11. {
  12.       for(int i=3; i*i<=mx; i+=2)
  13.       {
  14.           if(vis[i]==0)
  15.           {
  16.               for(int j = i*i; j<mx; j+=2*i)
  17.               vis[j]=1;
  18.           }
  19.       }
  20.  
  21.       prime.pb(2);
  22.       for(int i=3; i<mx; i+=2)
  23.         if(vis[i]==0)prime.pb(i);
  24. }
  25.  
  26.  
  27.  
  28.  
  29. int main()
  30. {
  31.    
  32.      sieve();
  33.        
  34.       int n;
  35.       while(cin>>n)
  36.       {
  37.          if(n==0)return 0;
  38.          int arr[n+5]={0};
  39.          for(int i=0; prime[i]<=n; i++)
  40.          {
  41.               int x = prime[i];
  42.             while(1)
  43.             {
  44.               if(x<=n)
  45.               {
  46.                 arr[prime[i]]++;
  47.               }
  48.               else break;
  49.               x*=prime[i];
  50.             }
  51.          }
  52.  
  53.         int ans = 1;
  54.          for(int i=2; i<=n; i++)
  55.          {
  56.             if(arr[i])
  57.             {
  58.               int x = arr[i];
  59.               while(x--)
  60.               {
  61.                 ans*=i;
  62.               }
  63.             }
  64.          }
  65.        
  66.           while(1)
  67.           {
  68.             if(ans%10!=0)
  69.             {
  70.               cout<<ans%10<<endl;
  71.               break;
  72.             }
  73.             ans/=10;
  74.           }
  75.       }
  76.     return 0;
  77. }
RAW Paste Data