Advertisement
hanst99

Find least common multiple (C++)

May 26th, 2011
584
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.08 KB | None | 0 0
  1. #include <map>
  2. #include <vector>
  3. #include <cmath>
  4.  
  5. const int NUMBER = 20;
  6.  
  7. bool isPrime(int number);
  8. int getNextPrime(int number);
  9. std::map<int, int> getPrimeFactors(int number);
  10. int getRangeLeastCommonMultiple(int maxNumber);
  11.  
  12. //This program finds the smallest number that is evenly divisible by all numbers from 1 to NUMBERS
  13. int main()
  14. {
  15.     return getRangeLeastCommonMultiple(NUMBER);
  16. }
  17.  
  18. bool isPrime(int number)
  19. {
  20.     if(number == 2)
  21.     {
  22.         return true;
  23.     }
  24.     else
  25.     {
  26.         for(int i=3; i<number; i+=2)
  27.         {
  28.             if(number %i == 0)
  29.             {
  30.                 return false;
  31.             }
  32.         }
  33.     }
  34.     return true;
  35. }
  36.  
  37. int getNextPrime(int number)
  38. {
  39.     do
  40.     {
  41.         ++number;
  42.     } while(!isPrime(number));
  43.     return number;
  44. }
  45.  
  46. std::map<int, int> getPrimeFactors(int number)
  47. {
  48.     std::map<int, int> factors;
  49.     for(int i=2; number>1; i=getNextPrime(i))
  50.     {
  51.         while(!(number%i))
  52.         {
  53.             number/=i;
  54.             if(factors.find(i)==factors.end())
  55.             {
  56.                 factors[i]=1;
  57.             } else
  58.             {
  59.                 ++(factors[i]);
  60.             }
  61.         }
  62.     }
  63.     return factors;
  64. }
  65.  
  66. int getRangeLeastCommonMultiple(int maxNumber)
  67. {
  68.     //get the prime factor representations of all numbers from 2 to the max number
  69.     std::vector<std::map<int,int>> primeFactorRepresentations;
  70.         for(int i=2; i<=maxNumber; ++i)
  71.     {
  72.         primeFactorRepresentations.push_back(getPrimeFactors(i));
  73.     }
  74.    
  75.     //get the highest exponent of each prime factor
  76.     std::map<int, int> factorList;
  77.     for(auto primeFactors = primeFactorRepresentations.begin();
  78.         primeFactors != primeFactorRepresentations.end(); ++primeFactors)
  79.     {
  80.         for(auto factor = (*primeFactors).begin(); factor != (*primeFactors).end(); ++factor)
  81.         {
  82.             auto fac = factorList.find((*factor).first);
  83.             if(fac == factorList.end())
  84.             {
  85.                 factorList[(*factor).first] = (*factor).second;
  86.             }
  87.             else if((*factor).second > (*fac).second)
  88.             {
  89.                 factorList[(*factor).first] = (*factor).second;
  90.             }
  91.         }
  92.     }
  93.    
  94.     int evenDivNumber = 1;
  95.         for(auto factor = factorList.begin(); factor!= factorList.end(); ++factor)
  96.     {
  97.         evenDivNumber *= std::pow((double) (*factor).first, (*factor).second);
  98.     }
  99.     return evenDivNumber;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement