Project Euler/5 - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:47:30Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:47, 9 October 2019
Line 1:		Line 1:
	Problem 5 on Project Euler: https://projecteuler.net/problem=5		Problem 5 on Project Euler: https://projecteuler.net/problem=5

	Solution: https://charlesreid1.com~~:3000~~/cs/euler/src/master/005		Solution: https://git.charlesreid1.com/cs/euler/src/master/005

	==Project Euler Problem 5==		==Project Euler Problem 5==
Line 13:		Line 13:
	Project Euler Link: https://projecteuler.net/problem=5		Project Euler Link: https://projecteuler.net/problem=5

	Solution code on git.charlesreid1.com link: https://charlesreid1.com~~:3000~~/cs/euler/src/master/Problem005.java		Solution code on git.charlesreid1.com link: https://git.charlesreid1.com/cs/euler/src/master/Problem005.java

	==Notes==		==Notes==

Admin: /* Illustrative Example */

2017-07-08T08:41:49Z

Illustrative Example

← Older revision		Revision as of 08:41, 8 July 2017
Line 70:		Line 70:
	We can also form 6 out of the same set, so we know that 60 is also the LCM of the first six integers.		We can also form 6 out of the same set, so we know that 60 is also the LCM of the first six integers.

	To get ~~teh~~ LCM of the first seven integers, 7 adds a new prime factor, so we get a new LCM of 420.		To get the LCM of the first seven integers, 7 adds a new prime factor, so we get a new LCM of 420.

	Getting the prime factorization of 8 requires one additional 2, so we get an LCM of 840, which is the product of 8 and 105.		Getting the prime factorization of 8 requires one additional 2, so we get an LCM of 840, which is the product of 8 and 105.



	==Flags==		==Flags==

Admin at 08:41, 8 July 2017

2017-07-08T08:41:37Z

← Older revision		Revision as of 08:41, 8 July 2017
Line 1:		Line 1:
	Problem 5 on Project Euler: https://projecteuler.net/problem=5		Problem 5 on Project Euler: https://projecteuler.net/problem=5

			Solution: https://charlesreid1.com:3000/cs/euler/src/master/005

	==Project Euler Problem 5==		==Project Euler Problem 5==
Line 41:		Line 43:

	So, we find any duplicate primes, like		So, we find any duplicate primes, like
	2 and 2^2, ~~and~~ replace them with just 2^2.		2 and 2^2, we replace them with just 2^2.

	If we find the prime representation of each integer,		If we find the prime representation of each integer,
Line 70:		Line 72:
	To get teh LCM of the first seven integers, 7 adds a new prime factor, so we get a new LCM of 420.		To get teh LCM of the first seven integers, 7 adds a new prime factor, so we get a new LCM of 420.

	Getting the prime factorization of 8 requires one ~~additoinal~~ 2, so we get an LCM of 840, which is the product of 8 and 105.		Getting the prime factorization of 8 requires one additional 2, so we get an LCM of 840, which is the product of 8 and 105.

Admin: Admin moved page Project Euler/LCM to Project Euler/5

2017-07-05T04:08:02Z

Admin moved page Project Euler/LCM to Project Euler/5

← Older revision	Revision as of 04:08, 5 July 2017
(No difference)

Admin at 09:06, 1 July 2017

2017-07-01T09:06:56Z

← Older revision		Revision as of 09:06, 1 July 2017
Line 1:		Line 1:
			Problem 5 on Project Euler: https://projecteuler.net/problem=5

	==Project Euler Problem 5==		==Project Euler Problem 5==

Admin: /* Flags */

2017-06-15T21:22:58Z

Flags

← Older revision		Revision as of 21:22, 15 June 2017
Line 77:		Line 77:

	[[Category:Primes]]		[[Category:Primes]]
	[[Category:~~Factorization~~]]		[[Category:Factoring]]
	[[Category:Math]]		[[Category:Math]]

Admin: /* Illustrative Example */

2017-06-15T21:22:12Z

Illustrative Example

← Older revision		Revision as of 21:22, 15 June 2017
Line 69:		Line 69:

	Getting the prime factorization of 8 requires one additoinal 2, so we get an LCM of 840, which is the product of 8 and 105.		Getting the prime factorization of 8 requires one additoinal 2, so we get an LCM of 840, which is the product of 8 and 105.



			==Flags==

			{{ProjectEulerFlag}}

			[[Category:Primes]]
			[[Category:Factorization]]
			[[Category:Math]]

Admin: /* Notes */

2017-06-15T21:21:43Z

Notes

← Older revision		Revision as of 21:21, 15 June 2017
Line 50:		Line 50:
	of a given integer (easy to do if we can get all the primes		of a given integer (easy to do if we can get all the primes
	up to that number).		up to that number).


			==Illustrative Example==

			Let's do this to find a least common multiple of a group of numbers.

			Start with the first three integers: 1, 2, and 3. (For our purposes, 1 doesn't contribute anything so we will not count it.

			Break down each number into its prime factorization: 2 => 2, 3 => 3. No prime factors are shared, so we multiply all the factors together and get an LCM of 6.

			For the first four integers, 1, 2, 3, 4, now 4 can be written as 2 * 2, so we write the minimum prime representation as 2 * 2 * 3, LCM is 12.

			On to first 5 integers: 1 2 3 4 5 break up into prime representation of 2, 3, 2 * 2, 5. The minimum set there is 2 * 2 * 3 * 5 or 60.

			We can also form 6 out of the same set, so we know that 60 is also the LCM of the first six integers.

			To get teh LCM of the first seven integers, 7 adds a new prime factor, so we get a new LCM of 420.

			Getting the prime factorization of 8 requires one additoinal 2, so we get an LCM of 840, which is the product of 8 and 105.

Admin: Created page with "==Project Euler Problem 5== Least common multiple problem. 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What i..."

2017-06-15T21:13:33Z

Created page with "==Project Euler Problem 5== Least common multiple problem. 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What i..."

New page

==Project Euler Problem 5==

Least common multiple 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?

Project Euler Link: https://projecteuler.net/problem=5

Solution code on git.charlesreid1.com link: https://charlesreid1.com:3000/cs/euler/src/master/Problem005.java

==Notes==

The naive approach is to simply say,
multiply all 20 integers together.
That gives you 20!, a very large number.

The next approach is to find the smallest
number that is evenly divisible by
all the integers i = 2 through n,
and if it is, print it out.

Unfortunately, while this integer is much
smaller than 20!, it is still too big
to find in a brute force for loop.

There must be a better way!

Indeed, this problem boils down to finding the
least common multiple, and a simple examination
of 5! = 120 reveals the right approach:

1*2*3*4*5 = 120 only has one repeated prime factor, a 2.

The least common multiple also happens
to be small enough to find in our head,
namely, 60, or 120/2.

So, we find any duplicate primes, like
2 and 2^2, and replace them with just 2^2.

If we find the prime representation of each integer,
then we find the minimum prime representation
shared by all of these integers, we will find
our least common multiple.

This will require getting a list of prime numbers
up to 20 (whew!), and the prime factors representation
of a given integer (easy to do if we can get all the primes
up to that number).