When I started Project Euler, I planned on every problem to be individualized and bundles of everything it takes for that one problem with no overlap. It didn't take long for me to get tired of cutting and pasting the same code over and over again, so I wrote a basic package with some basic tools for most of Project Euler's problems.
The obvious first method needed by more problems than any other code is determininig if a number is prime. I've done a lot of benchmarking and searching around and the implementation I've come up with is the fastest I have right now. Using the method is easy enough: pass it a number and the method returns true or false indicating if the number is prime. The implimentation is a touch more complicated, but not hard to follow. First a number is checked to determine if it's even or if it is 1. If so, then it can only be prime if the candidate is 2. 1 is not considered prime, some problems might break if you consider 1 to be prime, and the only prime even number is 2. After this, I iterate from 3 to the square root of the candidate. The primes 3, 5, and 7 skip past the loop because the square root is less than 3 and will properly return that those numbers are prime, and even though the square roots of 4, 6, and 8 are smaller than 3 (and would skip the loop) are all caught before this loop. 9 is the first value that would enter the loop and eventually be found as not prime. I only went up to the square root to save on comparisons. If a number is not prime, one divisor will be below the square root of the candidate and the other divisor will be above it (unless the candidate is a perfect square and then both values are the square root, but it's also even and caught in the initial if statement). The method is overloaded for ints, longs and BigIntegers.
Next is a method to return the number of divisors a number has without actually finding those divisors. This was a big help one an early problem but I included it here in case I need it again later. Using prime factorization and a little trick I read about on eHow, I made a quick translation to code and threw it in. In this, first I determine if the number is prime. If so, it has 2 divisors: itself and 1. If it's not prime, I start with the first prime, 2, and determine how many times it can be divided by it, dividing the value each time. Whether the prime divided in or not, I added 1 that number and multiplied it into a running total. Then I move to the next prime and continue through the loop until the value is reduced to 1. At that point, I have a total of divisors.
Greatest Common Divisor/Denominator and Factorial are both basic functions that we should all know how to code by now. I'll save you the trouble of explaining them, but they are definitely necessary for many problems.
Next comes some pretty specific string manipulation methods: IsPalindrome, IsPandigital, GetPandigital, IsPermutation, and AllCharactersUnique. They seem very specific but oddly they can be reused quite a bit. First a reminder on what Palindromes, Pandigital numbers, and Permutations are. Palindromes are words that can be read forward or backwards, racecar is the usual example of one. Pandigital numbers are X digit numbers that contain the numbers 1 to X. For example 632415 is pandigital while 135267 is not. Permutations are groups of data points in a particular order (remember that combinations have no order). IsPalindrome and IsPandigital are simple yes/no tests for a passed value. IsPalindrome is not limited to numbers while Pandigital will throw an index out of bounds exception if any character is non-numeric. GetPandigital is a magic function used by a particular problem. From one permutation, it jumps to another permutation. Please don't ask me to explain it. I was working with a friend and I was really in the zone at the time, now I just trust that it works. AllCharactersUnique answers the all too obvious question of "Are all characters in this string unique?" It's case sensitive, but I don't think case is an issue in the problems that would benefit from this function.
Periodically through the problems, Triangle and Square numbers are referenced. Pentagonal, Hexagonal, Heptagonal and Octagonal are referenced less often but nonetheless were added to the class. All of their equations come from Problem 61. They are all "GetNth..." versions so you can ask for particular indexed values. If they later ask to test if a number is any one of these, I'll write those methods then, but I don't want to fill this class with "Maybe someday I'll need this" material, so until then there is no check for if a number is one of these.
Spoiler : Utils.cs :
using System;
using System.Linq;
using System.Numerics;
namespace Utility {
public static class Utils {
/// <summary>
/// Tests if a candidate number is prime
/// </summary>
/// <param name="candidate">Number to test if prime</param>
/// <returns>True if candidate is prime, False otherwise</returns>
public static bool IsPrime(int candidate) {
if ((candidate & 1) == 0 || candidate == 1) {
return candidate == 2;
}
int sqrt = (int)Math.Sqrt(candidate);
for (int i = 3; i <= sqrt; i += 2) {
if ((candidate % i) == 0) {
return false;
}
}
return true;
}
/// <summary>
/// Tests if a candidate number is prime
/// </summary>
/// <param name="candidate">Number to test if prime</param>
/// <returns>True if candidate is prime, False otherwise</returns>
public static bool IsPrime(long candidate) {
if ((candidate & 1) == 0 || candidate == 1) {
return candidate == 2;
}
long sqrt = (long)Math.Sqrt(candidate);
for (long i = 3; i <= sqrt; i += 2) {
if ((candidate % i) == 0) {
return false;
}
}
return true;
}
/// <summary>
/// Tests if a candidate number is prime
/// </summary>
/// <param name="candidate">Number to test if prime</param>
/// <returns>True if candidate is prime, False otherwise</returns>
public static bool IsPrime(BigInteger candidate) {
if ((candidate & 1) == 0 || candidate == 1) {
return candidate == 2;
}
for (BigInteger i = 3; i * i <= candidate; i += 2) {
if ((candidate % i) == 0) {
return false;
}
}
return true;
}
/// <summary>
/// Returns the number of divisors for a given number
/// </summary>
/// <param name="val">The number to count divisors of</param>
/// <returns>The number of divisors</returns>
public static long CountDivisors(long val) {
long count = 1;
long prime = 2;
if (Utils.IsPrime(val)) {
count = 2;
val = 1;
}
while (val > 1) {
long temp = 0;
while (val % prime == 0) {
temp++;
val /= prime;
}
temp++;
count *= temp;
do {
if (prime == 2) {
prime++;
} else {
prime += 2;
}
} while (!Utils.IsPrime(prime));
}
return count;
}
/// <summary>
/// Find the Greatest Common Divisor of two numbers
/// </summary>
/// <param name="a">One number for finding divisor</param>
/// <param name="b">A second number for finding divisor</param>
/// <returns>The Greatest Common Divisor</returns>
public static int GCD(int a, int b) {
if (b > a) {
int temp = a;
a = b;
b = temp;
}
int c = a % b;
while (c != 0) {
a = b;
b = c;
c = a % b;
}
return b;
}
/// <summary>
/// Find the Greatest Common Divisor of two numbers
/// </summary>
/// <param name="a">One number for finding divisor</param>
/// <param name="b">A second number for finding divisor</param>
/// <returns>The Greatest Common Divisor</returns>
public static long GCD(long a, long b) {
if (b > a) {
long temp = a;
a = b;
b = temp;
}
long c = a % b;
while (c != 0) {
a = b;
b = c;
c = a % b;
}
return b;
}
/// <summary>
/// Computes factorial for given number
/// </summary>
/// <param name="val">Number to compute factorial for</param>
/// <returns>Result of factorial</returns>
public static int Factorial(int val) {
int ret = 1;
for (int i = val; i > 1; i--) {
ret *= i;
}
return ret;
}
/// <summary>
/// Computes factorial for given number
/// </summary>
/// <param name="val">Number to compute factorial for</param>
/// <returns>Result of factorial</returns>
public static long Factorial(long val) {
long ret = 1;
for (long i = val; i > 1; i--) {
ret *= i;
}
return ret;
}
/// <summary>
/// Computes factorial for given number
/// </summary>
/// <param name="val">Number to compute factorial for</param>
/// <returns>Result of factorial</returns>
public static BigInteger Factorial(BigInteger val) {
BigInteger ret = 1;
for (BigInteger i = val; i > 1; i--) {
ret *= i;
}
return ret;
}
/// <summary>
/// Tests if passed String is a palindrome
/// </summary>
/// <param name="val">String to test</param>
/// <returns>True if String is palindrome, False otherwise</returns>
public static bool IsPalindrome(String val) {
int mid = (int)Math.Floor((double)val.Length / 2);
for (int i = 0; i < mid; i++) {
if (val[i] != val[val.Length - 1 - i]) {
return false;
}
}
return true;
}
/// <summary>
/// Determines if a string contains only the numbers 1 through 9
/// </summary>
/// <param name="str">String to test</param>
/// <returns>True if it contains only 1 - 9</returns>
public static bool IsPandigital(String str) {
try {
bool[] arr = new bool[str.Length];
foreach (char letter in str) {
arr[letter - '1'] = true;
}
return arr.All(x => x);
} catch {}
return false;
}
/// <summary>
/// Gets a pandigital number a number of jumps from the initial input
/// </summary>
/// <param name="initial">The initial pandigital number</param>
/// <param name="jumps">Number of jumps from initial pandigital number</param>
/// <returns>Pandigital that is jumps number away from given pandigital</returns>
public static long GetPandigital(String initial, int jumps) {
int length = initial.Length;
String output = "";
for (int i = initial.Length - 1; i >= 0; i--) {
int f = Utils.Factorial(i);
int n = jumps / f;
jumps -= f * n;
n %= initial.Length;
output += initial[n];
initial = initial.Remove(n, 1);
}
return long.Parse(output);
}
/// <summary>
/// Returns if A and B are permutations of each other
/// </summary>
/// <param name="A">A string to compare</param>
/// <param name="B">A string to compare</param>
/// <returns>True if A and B are made of same characters</returns>
public static bool IsPermutation(String A, String B) {
foreach (char letter in A) {
if (B.Contains(letter)) {
B = B.Remove(B.IndexOf(letter), 1);
} else {
return false;
}
}
return String.IsNullOrEmpty(B);
}
/// <summary>
/// Determines if every character is only used once
/// </summary>
/// <param name="val">String to check</param>
/// <returns>True if every character is only used once</returns>
public static bool AllCharactersUnique(String val) {
if (val.Length <= 1) return true;
for (int i = 0; i < val.Length - 1; i++) {
for (int j = i + 1; j < val.Length; j++) {
if (val[i] == val[j]) {
return false;
}
}
}
return true;
}
public static int GetNthTriangle(int n) {
return n * (n + 1) / 2;
}
public static int GetNthSquare(int n) {
return n * n;
}
public static int GetNthPentagonal(int n) {
return n * (3 * n - 1) / 2;
}
public static int GetNthHexagonal(int n) {
return n * (2 * n - 1);
}
public static int GetNthHeptagonal(int n) {
return n * (5 * n - 3) / 2;
}
public static int GetNthOctagonal(int n) {
return n * (3 * n - 2);
}
}
}