Project Euler Problem 77 Solution

Project Euler Problem 77 Solution

Prime Summations

by {BetaProjects} | Project Euler & HackerRank

Project Euler Problem 77 Statement

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?

Solution

The core algorithm for this problem is strikingly similar to Project Euler Problem 31, where we calculate the number of ways to make change using a set of coins. Here, instead of coins, we use prime numbers.

The key difference lies in how we use the results. In Problem 31, we simply need the final count given a total (£2). However, for Problem 77, we need to find the first number that can be expressed as the sum of primes in more than 5,000 ways. Since our algorithm already generates the counts in ascending order, we can efficiently pinpoint the solution by searching for the first value in our results (ways[]) that exceeds 5,000.

Project Euler

local_min(ways, L) searches through the ways[] array to find the first occurrence of a value that meets or exceeds the given limit, L. The function returns both the index of this value and the value itself.

local_min = lambda n, L: next(((i, j) for i, j in enumerate(n) if L <= j), None)
L = 5000
print (local_min(ways, L)) #print the index and its value

This code would simply replace the last two lines of the code below.

HackerRank version

HackerRank logo

Solves all test cases for Hackerrank Project Euler Problem 77

HackerRank Project Euler 77 asks a completely different question. They want the number of different ways 2≤N≤1000 can be written as a sum of 1 or more primes for up to 100 test cases.

Python Source Code

import Euler
target = 1000
primes = Euler.prime_sieve(target)
ways = [1] + [0]*target
for p in primes:
    for i in range(p, target+1):
        ways[i]+= ways[i-p]
for _ in range(int(input())):
    print (ways[int(input())])

Last Word