Tag: Primes

It has been almost two years since I tackled Project Euler Problems One and Two. I really wanted to get back into it, so there really is no time like the present to do the work. I’m on my Mac Mini right now, so I developed this in C#.Net using MonoDevelop.

This problem needs us to find the largest prime factor of a very large number. Obviously, to do this, you need to be able to generate a set of prime numbers to work with. I have an IsPrime method that uses a very brute force method (with the shortcut of only checking as high as the square root of the number). I Googled around for ways to generate primes and looked into the Sieve of Eratosthenes, but it was a little complicated for the time I had allotted myself to work on this problem (basically the ten minutes until I had to put my son to bed). Plus, it turns out that this entire piece of code runs in under a second on my several year old Mac Mini, so there was no need to optimize yet. I know that later Project Euler problems also deal in primes, so I may need to break it out then.

Once I had that method in place, it was really a simple matter of working up to the square root of the number in the problem, 600851475143, using the same shortcut. If the number in my loop was prime and evenly divided into our number, I stored it as the current largest number. When I was done, whatever number was currently in that variable was our champion. Pretty simple logic.

using System;

namespace ProjectEuler
{
	/// <summary>
	/// The prime factors of 13195 are 5, 7, 13 and 29.
	///  What is the largest prime factor of the number 600851475143 ?
	/// http://projecteuler.net/index.php?section=problems&id=3
	///
	/// The answer is 6857
	/// </summary>
	public class Problem3
	{
		protected static double number = 600851475143;
		
		public static void Main(string[] args)
		{
			double limit = Math.Floor(Math.Sqrt(number));
			double currentLargestPrime = 0;

			for (double i = 2; i <= limit; i++)
			{
				if (IsPrime(i) && (number % i == 0))
				{
					currentLargestPrime = i;
				}
			}			
			
			Console.WriteLine(currentLargestPrime);
		}

		public static bool IsPrime(double n)
		{
			if (n%2 == 0) return false;

			var upperLimit = Math.Floor(Math.Sqrt(n));

			for (double i = 3; i <= upperLimit; i++)
			{
				if (n % i == 0) return false;
			}

			return true;
		}
	}
}

Have you attempted this problem yet? What is your solution? I’d love to see them. You can post it in the comments or post a link if you’ve blogged it already.