67 lines
1.3 KiB
Python
67 lines
1.3 KiB
Python
#!/usr/bin/python
|
|
|
|
# It is possible to write ten as the sum of primes in exactly five different ways:
|
|
#
|
|
# 7 + 3
|
|
# 5 + 5
|
|
# 5 + 3 + 2
|
|
# 3 + 3 + 2 + 2
|
|
# 2 + 2 + 2 + 2 + 2
|
|
#
|
|
# What is the first value which can be written as the sum of primes in over five thousand different ways?
|
|
|
|
from projecteuler import is_prime, timing
|
|
|
|
|
|
primes = [0] * 100
|
|
|
|
|
|
# Function using a simple recursive brute force approach to find all the partitions.
|
|
def count(value, n, i, target):
|
|
for j in range(i, 100):
|
|
value = value + primes[j]
|
|
|
|
if value == target:
|
|
return n + 1
|
|
|
|
if value > target:
|
|
return n
|
|
|
|
n = count(value, n, j, target)
|
|
value = value - primes[j]
|
|
|
|
return n
|
|
|
|
|
|
@timing
|
|
def p077():
|
|
# Generate a list of the first 100 primes.
|
|
i = 0
|
|
j = 0
|
|
|
|
while j < 100:
|
|
if is_prime(i):
|
|
primes[j] = i
|
|
j = j + 1
|
|
i = i + 1
|
|
|
|
i = 2
|
|
|
|
# Use a function to count the number of prime partitions for
|
|
# each number >= 2 until the one that can be written in over
|
|
# 5000 ways is found.
|
|
while True:
|
|
n = count(0, 0, 0, i)
|
|
|
|
if n > 5000:
|
|
break
|
|
|
|
i = i + 1
|
|
|
|
print('Project Euler, Problem 77')
|
|
print(f'Answer: {i}')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
p077()
|