Project Euler 27

Question: 

Euler discovered the remarkable quadratic formula:

n2+n+41

It turns out that the formula will produce 40 primes for the consecutive integer values 0≤n≤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≤n≤79The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n^2+an+b where |a|<1000 and |b|≤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.

문제:

오일러는 다음과 같은 놀랄만한 함수를 발견했다:

n2+n+41

이는 0≤n≤39 의 범위에서 40개의 연속적인 소수들을 계산한다. 하지만 n=40 일 때, 40^2+40+41=40(40+1)+41 는 41로 나누어 떨어지고, n = 41일 때,41^2+41+41 는 당연히 41 로 나누어 떨어진다.

엄청난 함수, n^2−79n+1601 가 발견되었는 데, 이는 0≤n≤79 범위에서 80개의 연속적인 소수들을 계산한다. 이 함수의 계수들의 곱, −79 and 1601, 은 −126479이다.

다음과 같은 형태의 2차 함수가 있다:

n^2+an+b ,|a|<1000 , |b|≤1000

|n| 은 n의 절대값이다.

예) |11|=11|and |−4|=4

n = 0 부터 시작하여, 가장 많은 연속적인 소수들을 계산하는 2차 함수의 계수,a 와 b,의 곱을 구하여라.

Solution:

from sympy import primerange, isprime
import time

primelist = list()
length = 0
aVal = int()
bVal = int()
start = time.time()

for a in range(-999,1000):
    for b in primerange(1,1001):
        do = True
        n = 0
        while do:
            number = n ** 2 + a * n + b
            if isprime(number) == False:
                do = False
                if len(primelist) > length:
                    length = len(primelist)
                    aVal = a
                    bVal = b
                else:
                    pass
                primelist = list()
                break
            else:
                primelist.append(number)
                n += 1   

print('''a = {0}\nb = {1}\nThe product of the coefficients: {2}
Formula: n^2 + {0}n + {1}
Found in ... {3:.2f}s'''.format(aVal,bVal,aVal * bVal,time.time() - start))

n = 0 일 때, f(n) = b 이므로 b 는 항상 소수여야 한다.

따라서 b 의 범위는 1 부터 1000 까지의 소수로 잡았다.

2019/01/29 - [Programming/python] - Module: sympy

1.34초 걸렸다!

-59231