Problem 27(Quadratic primes)

Problem 27(Quadratic primes)

Euler discovered the remarkable quadratic formula:

$$n^2+n+41$$

It turns out that the formula will produce \( 40 \) primes for the consecutive integer values \( 0 \leq n \leq 39 \). However, when \( n=40, \ \ 40^{2}+40+41=40(40+1)+41 \) is divisible by \( 41 \), and certainly when \( n=41, \ \ 41^{2}+41+41 \) is clearly divisible by \( 41 \).

The incredible formula \(n^{2}−79n+1601 \) was discovered, which produces \( 80 \) primes for the consecutive values \( 0 \leq n \leq 79 \) The product of the coefficients, \( −79 \)  and \( 1601\) , is \( −126479 \).

Considering quadratics of the form:

\( n^{2}+an+b \), where \( |a|<1000 \) and \( |b| \leq 1000 \)

where \( |n| \) is the modulus/absolute value of \( n \)
e.g. \( |11|=11 \)  and  \( |−4|=4 \)

Find the product of the coefficients,a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of \( n \), starting with \( n=0 \).

 

In Python:

import time

def formula(n, a, b):
    return n ** 2 + a * n + b

def isprime(n):
    for i in range(2, abs(int(n / 2)) + 1):
        if n % i == 0:
            return False
    return True


startTime = time.time()
maxNum = 0
product = 0
for a in range(-1000, 1001):
    for b in range(-1000, 1001):
        n = 0
        while(True):
            if isprime(formula(n, a, b)) is False:
                if n > maxNum:
                    maxNum = n
                    product = a * b
                break
            n += 1
print(maxNum, product)
print(time.time() - startTime, "seconds")

Run time: 22.622941970825195 seconds

 

In Python:

import time
import math

def formula(n, a, b):
    return n ** 2 + a * n + b

def isprime(n):
    for i in range(2, math.floor(math.sqrt(abs(n))) + 1):
        if n % i == 0:
            return False
    return True


startTime = time.time()
maxNum = 0
product = 0
for a in range(-1000, 1001):
    for b in range(-1000, 1001):
        n = 0
        while(True):
            if isprime(formula(n, a, b)) is False:
                if n > maxNum:
                    maxNum = n
                    product = a * b
                break
            n += 1
print(maxNum, product)
print(time.time() - startTime, "seconds")

Run time: 8.80458378791809 seconds

 

In Python:

import time
import math

def formula(n, a, b):
    return n ** 2 + a * n + b

def isprime(n):
    for i in range(2, math.floor(math.sqrt(abs(n))) + 1):
        if n % i == 0:
            return False
    return True


startTime = time.time()
maxNum = 0
product = 0
bList = [num for num in range(-1000, 1001) if isprime(num) is True]
for a in range(-1000, 1001):
    for b in bList:
        n = 0
        while(True):
            if isprime(formula(n, a, b)) is False:
                if n > maxNum:
                    maxNum = n
                    product = a * b
                break
            n += 1
print(maxNum, product)
print(time.time() - startTime, "seconds")

Run time: 3.3396518230438232 seconds

 

import time
import math

def formula(n, a, b):
    return n ** 2 + a * n + b

def isprime(n):
    for i in range(2, math.floor(math.sqrt(abs(n))) + 1):
        if n % i == 0:
            return False
    return True


startTime = time.time()
maxNum = 0
product = 0
aList = [num for num in range(-1000, 1001) if num % 2 == 1]
bList = [num for num in range(-1000, 1001) if isprime(num) is True]
for a in aList:
    for b in bList:
        n = 0
        while(True):
            if isprime(formula(n, a, b)) is False:
                if n > maxNum:
                    maxNum = n
                    product = a * b
                break
            n += 1
print(maxNum, product)
print(time.time() - startTime, "seconds")

Run time: 2.0211431980133057 seconds

 

In Java:

package project_euler21_30;

import java.util.ArrayList;

public class Euler27 {
	public static int formula(int n, int a, int b) {
		return (int)Math.pow(n, 2) + a * n + b;
	}
	public static boolean isprime(int n) {
		if (n == -1 || n == 0 || n == 1) {
			return false;
		} else {
			for (int i = 2; i < Math.floor(Math.sqrt(Math.abs(n)) + 2); i++) {
				if (n % i == 0){
					return false;
				}
			}
			return true;
		}
	}
	public static void main(String[] args) {
		long startTime = System.currentTimeMillis();
		int maxNum = 0;
		int product = 0;
		int n = 0;
		ArrayList<Integer> aList = new ArrayList<Integer>();
		ArrayList<Integer> bList = new ArrayList<Integer>();
		for (int i = -1000; i < 1001; i++) {
			if (i % 2 != 0) {
				aList.add(i);
			}
		}
		for (int i = -1000; i < 1001; i++) {
			if (isprime(i) == true) {
				bList.add(i);
			}
		}
		for (Integer a : aList) {
			for (Integer b : bList) {
				n = 0;
				while(true) {
					if (isprime(formula(n, a, b)) == false) {
						if (n > maxNum) {
							maxNum = n;
							product = a * b;
						}
						break;
					}
					n++;
				}
			}
		}
		System.out.println(product);
		long endTime = System.currentTimeMillis();
		System.out.println((double)(endTime - startTime)/(double)1000 + "seconds");
	}
}

Run time: 0.131seconds

 

Solution: -59231