Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <map>
- #include <vector>
- #include <cmath>
- const int NUMBER = 20;
- bool isPrime(int number);
- int getNextPrime(int number);
- std::map<int, int> getPrimeFactors(int number);
- int getRangeLeastCommonMultiple(int maxNumber);
- //This program finds the smallest number that is evenly divisible by all numbers from 1 to NUMBERS
- int main()
- {
- return getRangeLeastCommonMultiple(NUMBER);
- }
- bool isPrime(int number)
- {
- if(number == 2)
- {
- return true;
- }
- else
- {
- for(int i=3; i<number; i+=2)
- {
- if(number %i == 0)
- {
- return false;
- }
- }
- }
- return true;
- }
- int getNextPrime(int number)
- {
- do
- {
- ++number;
- } while(!isPrime(number));
- return number;
- }
- std::map<int, int> getPrimeFactors(int number)
- {
- std::map<int, int> factors;
- for(int i=2; number>1; i=getNextPrime(i))
- {
- while(!(number%i))
- {
- number/=i;
- if(factors.find(i)==factors.end())
- {
- factors[i]=1;
- } else
- {
- ++(factors[i]);
- }
- }
- }
- return factors;
- }
- int getRangeLeastCommonMultiple(int maxNumber)
- {
- //get the prime factor representations of all numbers from 2 to the max number
- std::vector<std::map<int,int>> primeFactorRepresentations;
- for(int i=2; i<=maxNumber; ++i)
- {
- primeFactorRepresentations.push_back(getPrimeFactors(i));
- }
- //get the highest exponent of each prime factor
- std::map<int, int> factorList;
- for(auto primeFactors = primeFactorRepresentations.begin();
- primeFactors != primeFactorRepresentations.end(); ++primeFactors)
- {
- for(auto factor = (*primeFactors).begin(); factor != (*primeFactors).end(); ++factor)
- {
- auto fac = factorList.find((*factor).first);
- if(fac == factorList.end())
- {
- factorList[(*factor).first] = (*factor).second;
- }
- else if((*factor).second > (*fac).second)
- {
- factorList[(*factor).first] = (*factor).second;
- }
- }
- }
- int evenDivNumber = 1;
- for(auto factor = factorList.begin(); factor!= factorList.end(); ++factor)
- {
- evenDivNumber *= std::pow((double) (*factor).first, (*factor).second);
- }
- return evenDivNumber;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement