Hmmm, I didn’t like this one as much. Probably because I never got to a solution that completed in a reasonable amount of time. This one took a few hours to run unfortunately. I believe I did what I could do to speed things up, with checking for the modulos of different numbers and whatnot. Looking at the forums after completing the problem, I see that others focused on the efficiency of their primality tests, some centering around prime probability tests like Miller-Rabin. This test is suppose to be quick and will tell you if the number is probably prime. Meaning that if it is probably prime, the next step would be to check if it actually is prime or not.
def isprimefactory(top):
sieve = [True] * (top + 1)
primes = []
for p, isprime in enumerate(sieve):
if not isprime or p < 2:
continue
primes.append(p)
num = p + p
while num <= top:
sieve[num] = False
num += p
def _isprime(n):
top = n**0.5
for p in primes:
if p > top:
return True
if n % p == 0:
return False
return True
return _isprime
primes = (27, 13, 9, 7, 3, 1)
composites = (5, 11, 15, 17, 19, 21, 23, 25)
mod11s = (1, 3, 5)
def solve(n):
isprime = isprimefactory(n + 6)
total = 0
for k in range(10, n, 10): # assumption: k is div by 10
if k > 10 and k % 7 != 4:
continue
k2 = k**2
if k2 % 210 != 100:
continue
if k2 % 11 not in mod11s:
continue
for p in primes:
if not isprime(k2 + p):
break
else:
for c in composites:
if isprime(k2 + c):
break
else:
total += k
return total
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
print(solve(n))
import pytest
from problem import solve
_test_solve = (
(11, 10),
(10**6, 1242490),
#(10**7, 11914460),
)
@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
assert expect == solve(n)