using System;
using System.Collections.Generic;
using System.Text;

namespace Euler3
{
    //Find the largest prime factor of a composite number.	
    class Program
    {
        private static List<long> _staPrimes;
        static void Main(string[] args)
        {
           
            long n = 600851475143;
            long product = 1;

            long largest = 0;


            //Brutal and dumb prime factorization
            _staPrimes = new List<long>();
            long inc = 4;
            //Hint #0: start with 3 then consider only odd numbers (remove multiples of 2)
            //Hint #1: start with 5 then increments by 2 then 4 (remove multiples of 2 and 3)
            for (long i = 5; product < n; i += inc)
            {
                if (isPrime(i))
                {
                    if (n % i == 0)
                    {
                        Console.Write(" " + i);
                        largest = i;

                        //Hint #3: check the result before burning your CPU, you dumbass!
                        product *= i;
                    }
                }
                if (inc == 2) inc = 4; else inc = 2;
            }

            Console.WriteLine("\nlargest: " + largest);
        }

        private static bool isPrime(long i)
        {
            //Hint #2: Compare only with primes up to the sqrt of the candidate
            for (int j = 0;( (j < _staPrimes.Count) && (_staPrimes[j] * _staPrimes[j] <= i)); ++j)
            {
                if (i % _staPrimes[j] == 0)
                    return false;
            }
            _staPrimes.Add(i);
            return true;
        }
    }
}