Solution to Project Euler Problem 27: Quadratic primes - Euler discovered the remarkable quadratic formula: Find the product of the coefficients, and , for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

• Java Code

package sikademy;
/**
 *
 * @author Archangel Macsika
 * Copyright (c) Sikademy. All rights reserved
 */

public class SikademyEulerSolution {
	
	public String run() {
		int bestNum = 0;
		int bestA = 0;
		int bestB = 0;
		for (int a = -1000; a <= 1000; a++) {
			for (int b = -1000; b <= 1000; b++) {
				int num = numberOfConsecutivePrimesGenerated(a, b);
				if (num > bestNum) {
					bestNum = num;
					bestA = a;
					bestB = b;
				}
			}
		}
		return Integer.toString(bestA * bestB);
	}
	
	
	private static int numberOfConsecutivePrimesGenerated(int a, int b) {
		for (int i = 0; ; i++) {
			int n = i * i + i * a + b;
			if (n < 0 || isPrime(n))
				return i;
		}
	}

        // Tests whether the given non-negative integer is prime.
	public static boolean isPrime(int x) {
		if (x < 0)
			throw new IllegalArgumentException("Negative number");
		if (x == 0 || x == 1)
			return false;
		else if (x == 2)
			return true;
		else {
			if (x % 2 == 0)
				return false;
			for (int i = 3, end = sqrt(x); i <= end; i += 2) {
				if (x % i == 0)
					return false;
			}
			return true;
		}
	}

        public static int sqrt(int x) {
		if (x < 0)
			throw new IllegalArgumentException("Square root of negative number");
		int y = 0;
		for (int i = 1 << 15; i != 0; i >>>= 1) {
			y |= i;
			if (y > 46340 || y * y > x)
				y ^= i;
		}
		return y;
	}

	public static void main(String[] args) {
                SikademyEulerSolution solution = new SikademyEulerSolution();
		System.out.println(solution.run());
	}	
}

• Python Code

# 
# @author Archangel Macsika
# Copyright (c) Sikademy. All rights reserved.
# 

import itertools


def compute():
	ans = max(((a, b) for a in range(-999, 1000) for b in range(2, 1000)),
		key=count_consecutive_primes)
	return str(ans[0] * ans[1])


def count_consecutive_primes(ab):
	a, b = ab
	for i in itertools.count():
		n = i * i + i * a + b
		if not is_prime(n):
			return i

def sqrt(x):
	assert x >= 0
	i = 1
	while i * i <= x:
		i *= 2
	y = 0
	while i > 0:
		if (y + i)**2 <= x:
			y += i
		i //= 2
	return y

def is_prime_file(x):
	if x <= 1:
		return False
	elif x <= 3:
		return True
	elif x % 2 == 0:
		return False
	else:
		for i in range(3, sqrt(x) + 1, 2):
			if x % i == 0:
				return False
		return True


# Returns a list of True and False indicating whether each number is prime.
# For 0 <= i <= n, result[i] is True if i is a prime number, False otherwise.
def list_primality(n):
	# Sieve of Eratosthenes
	result = [True] * (n + 1)
	result[0] = result[1] = False
	for i in range(sqrt(n) + 1):
		if result[i]:
			for j in range(i * i, len(result), i):
				result[j] = False
	return result

isprimecache = list_primality(1000)

def is_prime(n):
	if n < 0:
		return False
	elif n < len(isprimecache):
		return isprimecache[n]
	else:
		return is_prime_file(n)


if __name__ == "__main__":
	print(compute())