2020.10.19(pm): Sum of three different prime numbers

This article was written based on the Sample Problem of YBM COS Pro Level 1 Certification Exam.

Problem

You want to find a number that represents a number as the sum of 3 different decimals.

For example, 33 can be expressed in 4 ways.

3+7+23
3+11+19
3+13+17
5+11+17

Given a natural number n as a parameter, we want to write a solution function to return the number of ways that n is expressed as the sum of three different prime numbers. Fill in the blanks to complete the entire code.

※ There are 168 prime numbers less than 1,000.

Parameter description
n is given as a parameter to the solution function.

n is a natural number less than or equal to 1,000.

Return value description
Return the number of ways to express n as the sum of 3 different prime numbers.

If n cannot be expressed as the sum of 3 different prime numbers, please return 0.

Example explanation
Same as the example in Example #1.

Example #2 9 cannot be expressed as the sum of three different prime numbers.

# initial code
def solution(n):
    answer = 0
    primes = [2]
    for i in range (3, n + 1, 2) :
        is_prime = True
        for j in range(2, i) :
            if i % j == 0 :
                is_prime = False
                break
        if @@@ :
            primes.append(i)

    prime_len = len(primes)
    for i in range(0, prime_len - 2) :
        for j in range(i + 1, prime_len - 1) :
            for k in range(j + 1, prime_len) :
                if @@@ :
                    answer += 1
    return answer

# test code
n1 = 33
ret1 = solution(n1)

# output 1
print("The return value of solution function is", ret1)

n2 = 9
ret2 = solution(n2)

# output 2
print("The return value of solution function is", ret2)

Now what do we do here?

Looking at the first for statement, it says to repeat from 3 to n+1 at intervals of 2.
The process of adding the smallest number to the list of prime numbers and removing its multiples to find out the prime numbers less than n.
All you need to do is find and list all three combinations from the list of prime numbers.

The code is simple but difficult to understand at first.

Solution code is below. Check it out.

# solution code
def solution(n):
    answer = 0
    prime = []
    prime.append(2)
    for i in range (3, n+1, 2) :
        for j in range(2, i) :
            if i % j == 0 :
                break
        if j == i - 1:
            prime.append(i)
        
    prime_n = len(prime)
    for i in range(0, prime_n - 2) :
        for j in range(i + 1, prime_n - 1) :
            for k in range(j + 1, prime_n) :
                if prime[i] + prime[j] + prime[k] == n :
                    answer += 1
    
    return answer