91 lines
3.4 KiB
Python
91 lines
3.4 KiB
Python
#!/usr/bin/python
|
|
|
|
# The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime.
|
|
# For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes
|
|
# with this property.
|
|
#
|
|
# Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.
|
|
|
|
from projecteuler import is_prime, sieve, timing
|
|
|
|
|
|
@timing
|
|
def p060() -> None:
|
|
N = 10000
|
|
|
|
primes = sieve(N)
|
|
|
|
found = 0
|
|
p1 = 3
|
|
|
|
# Straightforward brute force approach
|
|
while p1 < N and not found:
|
|
# If p1 is not prime, go to the next number.
|
|
if primes[p1] == 0:
|
|
p1 = p1 + 2
|
|
continue
|
|
|
|
p2 = p1 + 2
|
|
|
|
while p2 < N and not found:
|
|
# If p2 is not prime, or at least one of the possible concatenations of
|
|
# p1 and p2 is not prime, go to the next number.
|
|
if primes[p2] == 0 or not is_prime(int(str(p1)+str(p2))) or not is_prime(int(str(p2)+str(p1))):
|
|
p2 = p2 + 2
|
|
continue
|
|
|
|
p3 = p2 + 2
|
|
|
|
while p3 < N and not found:
|
|
# If p3 is not prime, or at least one of the possible concatenations of
|
|
# p1, p2 and p3 is not prime, got to the next number.
|
|
if primes[p3] == 0 or not is_prime(int(str(p1)+str(p3))) or not is_prime(int(str(p3)+str(p1))) or\
|
|
not is_prime(int(str(p2)+str(p3))) or not is_prime(int(str(p3)+str(p2))):
|
|
p3 = p3 + 2
|
|
|
|
continue
|
|
|
|
p4 = p3 + 2
|
|
|
|
while p4 < N and not found:
|
|
# If p4 is not prime, or at least one of the possible concatenations of
|
|
# p1, p2, p3 and p4 is not prime, go to the next number.
|
|
if primes[p4] == 0 or not is_prime(int(str(p1)+str(p4))) or not is_prime(int(str(p4)+str(p1))) or\
|
|
not is_prime(int(str(p2)+str(p4))) or not is_prime(int(str(p4)+str(p2))) or\
|
|
not is_prime(int(str(p3)+str(p4))) or not is_prime(int(str(p4)+str(p3))):
|
|
p4 = p4 + 2
|
|
|
|
continue
|
|
|
|
p5 = p4 + 2
|
|
|
|
while p5 < N and not found:
|
|
# If p5 is not prime, or at least one of the possible concatenations of
|
|
# p1, p2, p3, p4 and p5 is not prime, go to the next number
|
|
if primes[p5] == 0 or not is_prime(int(str(p1)+str(p5))) or not is_prime(int(str(p5)+str(p1))) or\
|
|
not is_prime(int(str(p2)+str(p5))) or not is_prime(int(str(p5)+str(p2))) or\
|
|
not is_prime(int(str(p3)+str(p5))) or not is_prime(int(str(p5)+str(p3))) or\
|
|
not is_prime(int(str(p4)+str(p5))) or not is_prime(int(str(p5)+str(p4))):
|
|
p5 = p5 + 2
|
|
|
|
continue
|
|
|
|
# If it gets here, the five values have been found.
|
|
n = p1 + p2 + p3 + p4 + p5
|
|
found = 1
|
|
|
|
p4 = p4 + 2
|
|
|
|
p3 = p3 + 2
|
|
|
|
p2 = p2 + 2
|
|
|
|
p1 = p1 + 2
|
|
|
|
print('Project Euler, Problem 60')
|
|
print(f'Answer: {n}')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
p060()
|