Euler.cpp

#include <stdio.h>
#include <iostream>
#include <sstream>
#include <vector>
#include <string.h>
#include <time.h>
#include <algorithm>
#include <bitset>

using namespace std;

bool found = false;	//Used in problem 11 as a common variable

/*Adds all of the numbers between 1 and 1000 that are divisible by 3 or 5 (not exclusive) */
void Problem1()
{
	int total = 0;

	for(int i = 0; i < 1000; i++)
		if((i % 3 == 0) || (i % 5 == 0))	//Checks for divisability of three and five
			total += i;

	cout << "The total is of numbers divisible by 3 and 5 less than 1000 is " << total << endl;
};

/*Adds all of the even fibonnaci numbers (actual values, not place) that are less than 4 million) */
void Problem2()
{
	vector<int> fibNumbers = vector<int>();	//"Dynamic programming" approach to fibonacci numbers
	fibNumbers.push_back(1);
	fibNumbers.push_back(1);

	int accessor = 1;
	int total = 0;

	while(fibNumbers[accessor] < 4000000)
	{
		if(fibNumbers[accessor] % 2 == 0)
			total += fibNumbers[accessor];
		fibNumbers.push_back(fibNumbers[accessor-1] + fibNumbers[accessor]);
		++accessor;
	}

	cout << "The total of even numbered fibonnacci numbers less than 4 million is " << total << endl;
};

/* Checks if some large number is prime, helper for Problem3 */
bool checkPrime(long long input)
{
	if(input == 2)
		return true;
	else if(input % 2 == 0)
		return false;

	for(long long i = 3; i < (pow(input, 0.5) + 1); i++)
		if(input % i == 0)	//If any number between 2 and input-1 can divide into input evenly, the number isn't prime
			return false;

	return true;	//If no number between 2 and input-1 divide into input, then it's prime!
};

/* Recursively factors some large number. The largest prime factor will be found when input is prime. */
long long Problem3(long long input)	//Must be called with some input number
{
	if(checkPrime(input))	//A performance hit :(
		return input;
	else
		for(long long i = 2; i < input; i++)
			if(input % i == 0)	//Checks for factors
			{
				input /= i;	
				checkPrime(input);
				return Problem3(input);
			}
};

/*Converts an integer to a string using stringstream */
string intToString(int input)
{
	stringstream tempStream;
	tempStream << input;
	return tempStream.str();
};

/*A recursive method that checks if some string is a palindrome */
bool isPalindrome(string input)
{
	if(input.length() == 0 || input.length() == 1)	//Empty and 1-character strings are palindromes
		return true;
	if(input.at(0) == input.at(input.length() - 1)) //Strings are palindromes iff their first and last characters match
		return isPalindrome(input.substr(1, input.length() - 2));
	else
		return false;
};

/*Overloaded method allows you to check if an integer is a palindrome */
bool isPalindrome(int input)
{
	return isPalindrome(intToString(input));
};

/*Very innefficient. Works in n-squared time, where n is 900 */
int Problem4()
{
	int largest = 0;

	for(int i = 100; i < 1000; i++)
	{
		for(int j = 100; j < 1000; j++)
		{
			if(isPalindrome(i * j))
				if(largest < i * j)
				{
					cout << i << " " << j << endl;
					largest = i * j;
				}
		}
	}

	return largest;
};

/*Takes in some number and a list of numbers. Factors the number by the numbers already in the list, adds remaining number to the list */
void factorFinder(int input, vector<int> &list)
{
	if(list.size() == 0)
		list.push_back(input);
	else
	{
		for(int i = 0; i < list.size(); i++)
		{
			if(input % list[i] == 0)	//If some factor exists in the list, divide the input value by it
			{
				input = input / list[i];
			}
		}
		if(input != 1)	//Not necessary, but removes un-needed 1's from the list
			list.push_back(input);
	}
};

/*Overloaded function for factorFinder, takes in a factor list and some number that you want to find factors from 1 - to */
void factorFinder(vector<int> &list, int numTimes)
{
	for(int i = 1; i <= numTimes; i++)
		factorFinder(i, list);
};

/*Creates a vector of factors that will be multiplied together to find the smallest numbers evenly divisible by all numbers from 1 - 20 */
long long Problem5()
{
	vector<int> factorList = vector<int>();

	long long smallestProduct = 1;

	factorFinder(factorList, 20);	//20 can be changed to any number

	for(int i = 0; i < factorList.size(); i++)
		smallestProduct *= factorList[i];

	return smallestProduct;

};

/*Inefficient, can be done with math trickery and simplification */
long long Problem6(int input)
{
	long long sumOfSquares = 0;
	long long squareOfSums = 0;

	for(int i = 1; i <= 100; i++)
	{
		sumOfSquares += i ^ 2;
		squareOfSums += i;
	}

	squareOfSums *= squareOfSums;

	return abs(sumOfSquares - squareOfSums);
};

/*Inefficient, brute-force way of finding the input'th prime number */
long long Problem7(int input)
{
	long long tempPrime = 2;
	time_t time1 = clock();
	for(int i = 1; i < input; i++)
	{
		++tempPrime;
		while(!checkPrime(tempPrime))
			++tempPrime;

	}
	time_t elapsed = clock() - time1;
	cout << "Completed in " << elapsed << " milliseconds." << endl;

	return tempPrime;
};

/*
long long EfficientProblem7(int input)
{
	vector<long long> primes = vector<long long>();

	primes.push_back(2);

	long long tempPrime;
	long long multiplier;

	for(int i = 1; i <= input; i++)
	{
		tempPrime = primes[0];
		while(tempPrime <= primes[primes.size() - 1])
		{
			if(checkPrime(tempPrime+1))
				primes.push_back(++tempPrime);
			
		}


	}
}
*/

/*Finds the largest product of five consecutive digits of some large number */
int Problem8()
{
	string largeNumAsString = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
	//char * largeNum = new char[largeNumAsString.size()];
	//memcpy(largeNum, largeNumAsString.c_str(), largeNumAsString.size());

	int largestProduct = 0;
	int tempProduct = 0;
	for(int i = 0; i < largeNumAsString.size() - 4; i++)
	{
		tempProduct = largeNumAsString[i] - 48;

		for(int j = i + 1; j < (i + 5); j++)
			tempProduct *= (largeNumAsString[j] - 48);
		
		if(tempProduct > largestProduct)
			largestProduct = tempProduct;
	}

	return largestProduct;
};

/*Pythagorean triplets */
int Problem9(int input = 1000)
{
	int a = 1;
	int b = 2;
	int c = 3;
	while(c < input)
	{
		while(b < c)
		{
			while(a < b)
			{
				if((a * a + b * b) == (c * c) && a + b + c == input) 
					return a * b * c;
				else
					++a;
			}
			++b;
			a = 1;	//resets a
		}
		a = 1;
		b = 2;	//resets a and b
		++c;
	}
};

long long Problem10()
{
	long long primeTotal = 0;

	for(int i = 2; i < 2000000; i++)
		if(checkPrime(i))
			primeTotal += i;

	return primeTotal;
}

long long Problem10Sieve()
{
	bitset<2000000> Sieve;   
	long long sum = 0;   Sieve.flip();    // Set all bits to 1   
	Sieve[0].flip();  // Set 0 and 1 to not prime   
	Sieve[1].flip();   
	// Check all nos from 2 to 1 million   
	for(long i = 2; i < 2000000; ++i)   
	{     
		if(!Sieve[i] )  // If marked not prime       
			continue;    // return to head of loop     
		else       // Set all multiples as not prime       
			for(long j = 2*i; j < 2000000; j += i)         
				Sieve[j] = 0;   
	}   
	for(long i = 2; i < 2000000; ++i)     
		if( Sieve[i] )  // Add all nos with bit set       
			sum += i;   
	return sum;  
}

/* Very quick and dirty */
int findFour(int fourArray[20][20])
{
	int largest = 0;
	for(int i = 0; i < 20; i++)
	{
		for(int j = 0; j < 20; j++)
		{
			if(fourArray[i][j] != 0 && (i < 17 && j < 17))
			{
				if(fourArray[i+1][j] != 0 && fourArray[i+2][j] != 0 && fourArray[i+3][j] != 0)
				{
					if(fourArray[i][j] * fourArray[i+1][j] * fourArray[i+2][j] * fourArray[i+3][j] > largest)
					{
						largest = fourArray[i][j] * fourArray[i+1][j] * fourArray[i+2][j] * fourArray[i+3][j];
						found = true;
					}
				}
				if(fourArray[i+1][j+1] != 0 && fourArray[i+2][j+2] != 0 && fourArray[i+3][j+3] != 0)
				{
					if(fourArray[i][j] * fourArray[i+1][j+1] * fourArray[i+2][j+2] * fourArray[i+3][j+3] > largest)
					{
						largest = fourArray[i][j] * fourArray[i+1][j+1] * fourArray[i+2][j+2] * fourArray[i+3][j+3];
						found = true;
					}
				}
				if(fourArray[i][j+1] != 0 && fourArray[i][j+2] != 0 && fourArray[i][j+3] != 0)
				{
					if(fourArray[i][j] * fourArray[i][j+1] * fourArray[i][j+2] * fourArray[i][j+3] > largest)
					{
						largest = fourArray[i][j] * fourArray[i][j+1] * fourArray[i][j+2] * fourArray[i][j+3];
						found =  true;
					}
				}
			}
			if(fourArray[i][j] != 0 && (i > 2 && j > 2))
				if(fourArray[i-1][j+1] != 0 && fourArray[i-2][j+2] != 0 && fourArray[i-3][j+3] != 0)
					if(fourArray[i][j] * fourArray[i-1][j+1] * fourArray[i-2][j+2] * fourArray[i-3][j+3] > largest)
						{
							largest = fourArray[i][j] * fourArray[i-1][j+1] * fourArray[i-2][j+2] * fourArray[i-3][j+3];
							found =  true;
						}
		}
	}

	return largest;
}

int Problem11()
{
	time_t startTime = clock();

	int largest = 0;

	int numberArray[20][20] = 
	{
		8, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 8, 
		49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 04, 56, 62, 00,
		81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 03, 49, 13, 36, 65,
		52, 70, 95, 23, 04, 60, 11, 42, 69, 24, 68, 56, 01, 32, 56, 71, 37, 02, 36, 91,
		22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80,
		24, 47, 32, 60, 99, 03, 45, 02, 44, 75, 33, 53, 78, 36, 84 ,20, 35, 17, 12, 50,
		32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70,
		67, 26, 20, 68, 02, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21,
		24, 55, 58, 05, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72,
		21, 36, 23, 9, 75, 00, 76, 44, 20, 45, 35, 14, 00, 61, 33, 97, 34, 31, 33, 95,
		78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 03, 80, 04, 62, 16, 14, 9, 53, 56, 92,
		16, 39, 05, 42, 96, 35, 31, 47, 55, 58, 88, 24, 00, 17, 54, 24, 36, 29, 85, 57,
		86, 56, 00, 48, 35, 71, 89, 07, 05, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58,
		19, 80, 81, 68, 05, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 04, 89, 55, 40,
		04, 52, 8, 83, 97, 35, 99, 16, 07, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66,
		88, 36, 68, 87, 57, 62, 20, 72, 03, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69,
		04, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36,
		20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 04, 36, 16,
		20, 73, 35, 29, 78, 31, 90, 01, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 05, 54,
		01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48
	};

	int fourArray[20][20];

	//Initialize array
	for(int i = 0; i < 20; i++)
		for(int j = 0; j < 20; j++)
			fourArray[i][j] = 0;

	//Larger numbers multiplied together give you the largest values. Therefore, if you count down from the largest number, when you have a set of four, that's the largest possible product
	for(int counter = 100; counter > 0; counter--)
	{
		for(int i = 0; i < 20; i++)
			for(int j = 0; j < 20; j++)
			{
				if(numberArray[i][j] == counter)
					fourArray[i][j] = counter;	//Puts the large number into fourArray
			}
		largest = findFour(fourArray);//Checks to see if there are any sets of four in fourArray
		if(largest != 0)
		{
			time_t elapsed = clock() - startTime;
			cout << "Completed in " << elapsed << " milliseconds." << endl;
			return largest;
		}
	}

	return largest;
}

int findFactors(int input)
{
	int count = 0;
	for(long long i = 1; i < (int)ceil((pow(input, 0.5))); i++)
		if(input % i == 0)
			++count;

	return count;
}

long long triangleNumber(int input)
{
	if(input == 1)
		return 1;
	else
		return input + triangleNumber(input-1);
}

long long Problem12()
{
	long long largestTriangleNum = 0;
	long long temp = 0;
	for(int i = 1; i < 20000000; i++)
	{
		if(i % 2 == 1)
		{
			temp = i * (i / 2 + 1);

			if(findFactors(i) + findFactors(i / 2 + 1) > 500)
				return triangleNumber(i);

		}
		else
		{
			temp = (i + 1) * (i / 2);
			if(findFactors(i+1) + findFactors(i / 2) > 500)
				return triangleNumber(i);
		}
	}	

	return 0;
}


int main() 
{   
	cout << triangleNumber(12335) << endl;
	system("PAUSE");
	return 0; 
}