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