Project Euler/3 - Revision history

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

2019-10-09T03:47:10Z

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

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

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

	In this problem we are finding the largest prime factor of an integer.		In this problem we are finding the largest prime factor of an integer.

Admin at 08:32, 8 July 2017

2017-07-08T08:32:13Z

← Older revision		Revision as of 08:32, 8 July 2017
Line 3:		Line 3:
	Solution: https://charlesreid1.com:3000/cs/euler/src/master/003		Solution: https://charlesreid1.com:3000/cs/euler/src/master/003

	~~Finding~~ the largest prime factor of ~~a given~~ integer:		In this problem we are finding the largest prime factor of an integer.

			==Approach==

	This task is similar to finding the complete prime factorization, except in special cases. For example, 1118125 = 5^4 * 1789 - if we start our search for prime factors at 2, we'll get stuck dividing out all the 5s and get to the largest prime factor (1789) last.		This task is similar to finding the complete prime factorization, except in special cases. For example, 1118125 = 5^4 * 1789 - if we start our search for prime factors at 2, we'll get stuck dividing out all the 5s and get to the largest prime factor (1789) last.
Line 12:		Line 14:
	2. The number is a product of 2 and a prime number (maximizes size of other prime number).		2. The number is a product of 2 and a prime number (maximizes size of other prime number).

	So we should check if our number is prime, and start counting from halfway to the number down to 2, checking for perfect divisors. In the case of finding the largest prime factor, we quit when we find the first prime factor (the largest). In the case of finding the prime factorization of a number, we continue until we reach 1 (like Euclidean algorithm).		So we should check if our number is prime, and start counting from halfway to the number, counting down to 2, and checking for perfect divisors. In the case of finding the largest prime factor, we quit when we find the first prime factor (the largest). In the case of finding the prime factorization of a number, we continue until we reach 1 (like Euclidean algorithm).

			==Generalization==

			The generalization of what we're doing here is to pull out prime factors in a particular order - useful if there are a very large number of factors in a number. This functionality can be added to an Euler Library for use in later problems.

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Admin at 08:30, 8 July 2017

2017-07-08T08:30:42Z

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

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

	Finding the largest prime factor of a given integer:		Finding the largest prime factor of a given integer:

Admin: Admin moved page Project Euler/Largest Prime Factor to Project Euler/3

2017-07-05T04:07:38Z

Admin moved page Project Euler/Largest Prime Factor to Project Euler/3

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

Admin at 09:07, 1 July 2017

2017-07-01T09:07:16Z

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


	Finding the largest prime factor of a given integer:		Finding the largest prime factor of a given integer:

Admin at 20:57, 15 June 2017

2017-06-15T20:57:34Z

← Older revision		Revision as of 20:57, 15 June 2017
Line 9:		Line 9:

	So we should check if our number is prime, and start counting from halfway to the number down to 2, checking for perfect divisors. In the case of finding the largest prime factor, we quit when we find the first prime factor (the largest). In the case of finding the prime factorization of a number, we continue until we reach 1 (like Euclidean algorithm).		So we should check if our number is prime, and start counting from halfway to the number down to 2, checking for perfect divisors. In the case of finding the largest prime factor, we quit when we find the first prime factor (the largest). In the case of finding the prime factorization of a number, we continue until we reach 1 (like Euclidean algorithm).



			{{ProjectEulerFlag}}
			[[Category:Math]]
			[[Category:Primes]]
			[[Category:Prime Numbers]]
			[[Category:Factoring]]

Admin: Created page with "Finding the largest prime factor of a given integer: This task is similar to finding the complete prime factorization, except in special cases. For example, 1118125 = 5^4 * 1..."

2017-06-15T20:56:56Z

Created page with "Finding the largest prime factor of a given integer: This task is similar to finding the complete prime factorization, except in special cases. For example, 1118125 = 5^4 * 1..."

New page

Finding the largest prime factor of a given integer:

This task is similar to finding the complete prime factorization, except in special cases. For example, 1118125 = 5^4 * 1789 - if we start our search for prime factors at 2, we'll get stuck dividing out all the 5s and get to the largest prime factor (1789) last.

Rather, we should start at the integer itself, and work our way down. The worse cases are:

1. The number itself is prime, so we should check the number itself
2. The number is a product of 2 and a prime number (maximizes size of other prime number).

So we should check if our number is prime, and start counting from halfway to the number down to 2, checking for perfect divisors. In the case of finding the largest prime factor, we quit when we find the first prime factor (the largest). In the case of finding the prime factorization of a number, we continue until we reach 1 (like Euclidean algorithm).