function [] = Problem27()
%ProjectEuler/Octave/Problem27.m
%Matthew Ellison
% Created: 09-15-19
%Modified: 09-15-19
%Find the product of the coefficients, |a| < 1000 and |b| <= 1000, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n=0.
%{
	Copyright (C) 2019  Matthew Ellison

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU Lesser General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU Lesser General Public License for more details.

	You should have received a copy of the GNU Lesser General Public License
	along with this program.  If not, see <https://www.gnu.org/licenses/>.
%}


%Setup variables
topA = 0;
topB = 0;
topN = 0;
primeNums = primes(12000);

%Start timer
startTime = clock();


%Start with the lowest possible A and check all possibilities after that
for a = -999 : 999
	%Start with the lowest possible B and check all possibilities after that
	for b = -1000 : 1000
		%Start with n=0 and check the formula to see how many primes you can get get with concecutive n's
		n = 0;
		quadratic = (n * n) + (a * n) + b;
		while(isFound(primeNums, quadratic))
			++n;
			quadratic = (n * n) + (a * n) + b;
		end
		--n;

		%Set all the largest number if this creaed more primes than any other
		if(n > topN)
			topN = n;
			topB = b;
			topA = a;
		end
	end
end


%End the timer
endTime = clock();

%Print the results
printf("The greatest number of primes found is %d", topN)
printf("\nIt was found with A = %d, B = %d", topA, topB)
printf("\nThe product of A and B is %d\n", topA * topB)
printf("It took %f seconds to run this algorithm\n", etime(endTime, startTime))

end

function [found] = isFound(array, key)
	found = false;	%Start with a false. It only turns true if you find key in array
	for location = 1 : size(array)(2)
		if(key < array(location))
			return;
		elseif(key == array(location))
			found = true;
			return;
		end
	end
end

%{
Results:
The greatest number of primes found is 70
It was found with A = -61, B = 971
The product of A and B is -59231
It took 1298.651146 seconds to run this algorithm
%}