50 lines
1.2 KiB
Python
50 lines
1.2 KiB
Python
from lib_prime import is_prime_rabin_miller
|
|
import concurrent.futures
|
|
|
|
|
|
def follows_prime_pattern(n):
|
|
n2 = n * n
|
|
prev_prime = None
|
|
for i in [1, 3, 7, 9, 13, 27]:
|
|
p = n2 + i
|
|
if not is_prime_rabin_miller(p):
|
|
return False
|
|
if prev_prime is not None:
|
|
for x in range(prev_prime + 2, p, 2):
|
|
if is_prime_rabin_miller(x):
|
|
return False
|
|
prev_prime = p
|
|
return True
|
|
|
|
|
|
def check_range(n_min, n_max):
|
|
s = 0
|
|
for n in range(n_min - (n_min % 10), n_max, 10):
|
|
if n % 3 == 0:
|
|
continue
|
|
if follows_prime_pattern(n):
|
|
print(n)
|
|
s += n
|
|
return s
|
|
|
|
|
|
def euler_146():
|
|
s = 0
|
|
m = 150_000_000
|
|
range_size = 500_000
|
|
|
|
with concurrent.futures.ProcessPoolExecutor() as executor:
|
|
futures = []
|
|
for start in range(1, m, range_size):
|
|
end = min(start + range_size, m)
|
|
futures.append(executor.submit(check_range, start, end))
|
|
for future in concurrent.futures.as_completed(futures):
|
|
s += future.result()
|
|
return s
|
|
|
|
|
|
if __name__ == "__main__":
|
|
solution = euler_146()
|
|
print("e146.py: " + str(solution))
|
|
assert solution == 676333270
|