Untitled UI logotext
Solutions
WebsitesEcommerceMobile AppsWeb AppsProduction Support & Maintenance
Our work
Company
About usBlogPodcastContact us
Book a free consultation

Project Euler Problem 5

Olivia Rhye

I've been having some fun doing the first few problems of Project Euler and figured I'd share my solution to problem 5 here.  

The Problem
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.  What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

The Solution
This problem, worded another way, asks what the least common multiple of all the integers between 1 and 20 is.  Since multiplication is commutative, the least common multiple of a series is the same as computing the least common multiple of all the numbers before it and the current.  So, LCM(1...6) is the same as LCM(6, LCM(5, LCM(4, LCM(3, LCM(2, 1))))).  

#include 
using namespace std;

int main () {
        unsigned long sumsquares = 0, sums = 0;
        int n;

        cout <> n;

        while (n < 0) {
                cout <> n;
        }

        for(int i = 1; i <= n; i++) {
                cout << "i: " << i << endl;
                sumsquares += i * i;
                cout << "sumsquares: " << sumsquares << endl;
                sums += i;
                cout << "sums: " << sums << endl;
        }

        cout << "The sum of squares from 1 to " << n << ": " << sumsquares << endl;
        cout << "The square of sums from 1 to " << n << ": " << sums * sums << endl << endl;
        cout << "The difference: " << (sums * sums - sumsquares) << endl;

        return(0);
}

‍

My solution uses an algorithm to compute the least common multiple that involves finding the greatest common divisor as follows:  lcm(a, b) = a*b / gcd(a, b).  I used the Euclid method of finding the greatest common divisor:  gcd(a,0) = a; gcd(a, b) = gcd(b, a mod b).

Ready to start a project?

Book a free consultation
Untitled UI logotext
Our work
About us
Blog
Careers
Submit a ticket
Agency Partnerships
Contact
© 2024 fjorge. All rights reserved.
Privacy