using System;
using System.Collections.Generic;
using static System.Console;
using Xunit;

namespace Euler {

  public class Program {

  	[Fact]
  	static long Problem1() {
  		long sum = 0;
  		for (long i = 1; i < 1000; i++) {
  			if (i % 3 == 0 || i % 5 == 0) {
  				sum += i;
  			}
  		}
  		Assert.Equal(233168, sum);
  		return sum;
  	}

  	[Fact]
  	static long Problem2() {
  		long max = 4_000_000;

  		var fibs = new List<long>();
  		fibs.Add(1);
  		fibs.Add(2);

  		while (fibs[fibs.Count - 1] < max) {
  			long num = fibs[fibs.Count - 1] + fibs[fibs.Count - 2];
 			  fibs.Add(num);
  		}

      long sum = 0;
  		foreach (int i in fibs) {
  			if (i % 2 == 0 && i <= max) {
  				sum += i;
  			}
  		}

  		Assert.Equal(4613732, sum);
  		return sum;
  	}

  	static bool IsPrime(long num, List<long> primes) {
  		foreach (long i in primes) {
  			if (num % i == 0) {
  				return false;
  			}
  		}
  		return true;
  	}

  	static List<long> PrimesUpThrough(long num) {
  		var primes = new List<long>();
  		primes.Add(2);
  		for (int i = 3; i <= num; i += 2) {
  			if (IsPrime(i, primes)) {
  				primes.Add(i);
  			}
  		}
  		return primes;
  	}

  	static List<long> FirstNPrimes(long n) {
  		var primes = new List<long>();
  		primes.Add(2);
  		for (int i = 3; ; i += 2) {
  			if (IsPrime(i, primes)) {
  				primes.Add(i);
  				if (primes.Count == n) {
  					return primes;
  				}
  			}
  		}
  	}

    [Fact]
  	static long Problem3() {
  		long target = 600_851_475_143;
  		long targetSqrt = (long) Math.Sqrt(target);
  		List<long> primes = PrimesUpThrough(targetSqrt);
  		long highestPrimeFactor = 0;
  		foreach (long i in primes) {
  			if (target % i == 0) {
  				highestPrimeFactor = i;
  			}
  		}
  		Assert.Equal(6857, highestPrimeFactor);
  		return highestPrimeFactor;
  	}

  	static bool IsPalindromicNumber(long l) {
  		string s = "" + l;
  		for (int i = 0; i < s.Length / 2; i++) {
  			if (s[i] != s[s.Length - i - 1]) {
  				return false;
  			}
  		}
  		return true;
  	}

		[Fact]
  	static long Problem4() {
  		long largest = 0;
  		for (long i = 999; i >= 100; i--) {
  			for (long j = 999; j >= 100; j--) {
  				long target = i * j;
  				if (target < largest) {
  					continue;
  				}
  				if (IsPalindromicNumber(target)) {
  					largest = target;
  				}
  			}
  		}
  		Assert.Equal(906609, largest);
  		return largest;
  	}

		[Fact]
  	static long Problem5() {
  		for (long test = 20; ; test += 20) {
  			for (int i = 2; i <= 20; i++) {
  				if (test % i != 0) {
  					break;
  				}
  				if (i == 20) {
  					Assert.Equal(232792560, test);
  			    return test;
  			  }
  			}
  		}
  	}

    [Fact]
    static long Problem6() {
    	long sum = 0;
      long sumSq = 0;
    	for (long i = 1; i <= 100; i++) {
    		sum += i;
    		sumSq += i * i;
    	}
    	long result = sum * sum - sumSq;
    	Assert.Equal(25164150, result);
    	return result;
  	}

  	[Fact]
  	static long Problem7() {
  		List<long> primes = FirstNPrimes(10001);
  		long result = primes[primes.Count - 1];
  		Assert.Equal(104743, result);
  		return result;
  	}

    [Fact]
    static long Problem8() {
      string number =
          "73167176531330624919225119674426574742355349194934" +
          "96983520312774506326239578318016984801869478851843" +
          "85861560789112949495459501737958331952853208805511" +
          "12540698747158523863050715693290963295227443043557" +
          "66896648950445244523161731856403098711121722383113" +
          "62229893423380308135336276614282806444486645238749" +
          "30358907296290491560440772390713810515859307960866" +
          "70172427121883998797908792274921901699720888093776" +
          "65727333001053367881220235421809751254540594752243" +
          "52584907711670556013604839586446706324415722155397" +
          "53697817977846174064955149290862569321978468622482" +
          "83972241375657056057490261407972968652414535100474" +
          "82166370484403199890008895243450658541227588666881" +
          "16427171479924442928230863465674813919123162824586" +
          "17866458359124566529476545682848912883142607690042" +
          "24219022671055626321111109370544217506941658960408" +
          "07198403850962455444362981230987879927244284909188" +
          "84580156166097919133875499200524063689912560717606" +
          "05886116467109405077541002256983155200055935729725" +
          "71636269561882670428252483600823257530420752963450";
      int numDigits = 13;
      long maxProduct = 0;
      for (int i = 0; i < number.Length - numDigits; i++) {
        long product = 1;
        for (int j = i; j < i + numDigits; j++) {
          int digit = Int32.Parse(number.Substring(j, 1));
          product *= digit;
        }
        if (product > maxProduct) {
          maxProduct = product;
        }
      }
      Assert.Equal(23514624000, maxProduct);
      return maxProduct;
    }

    [Fact]
    static long Problem9() {
      for (int a = 1; a <= 333; a++) {
        for (int b = a + 1; b < 1000 - a; b++) {
          int c = 1000 - b - a;
          if (c < b) {
            break;
          }
          if (a * a + b * b == c * c) {
            int result = a * b * c;
            Assert.Equal(31875000, result);
            return result;
          }
        }
      }
      return 0;
    }

    [Fact]
    static long Problem10() {
      List<long> primes = PrimesUpThrough(2_000_000);
      long sum = 0;
      foreach (long prime in primes) {
        sum += prime;
      }
      Assert.Equal(142913828922, sum);
      return sum;
    }

    static void Main(string[] args) {
      WriteLine(Problem10());
    }
  }
}