Write an efficient algorithm in python to solve math problem

Question

I can't came up with an algorithm to solve the following problem:

1. Generate an array of first n prime numbers.
2. Remove k numbers from this array in such way that after concatenating all numbers left we get the largest possible result.

E.G.

Input: 4 2

• First value(4) is n

• Second value(2) is k

• Array [2, 3, 5, 7] is generated

• the program have to remove numbers 2 and 3 from this array(to get 57, which is the max possible number we can get from this array after deleting k numbers and merging all the numbers left together).
• e.g. If it removes 2 and 7 - we will get 35(which is not the max number). So, this solution is wrong.

Output: 57

This is the code I have so far:

def getInputedVals():
    return [int(el) for el in input().split(" ")]


def get_primes_array(x):
    primes = []
    a = 2

    # for a in range(2, 10000):
    while(len(primes) != x):
        for b in range(2, a):
            if a % b == 0:
                break
        else:
            primes.append(a)
        a += 1
        if len(primes) == x:
            return primes


def combine_numbers(nums):
    s = [str(i) for i in nums]
    return int("".join(s))


# Algorithm to find the max number should be written here
def get_result(nums, n_nums_to_delete):
    print("algorithm goes here")


def main(item):

    primes = get_primes_array(item["n_first"])
    summed = sum(primes)

    # print(get_result(primes, item["n_nums_to_delete"]))
    print("Primes: ", primes)


n_first, n_nums_to_delete = getInputedVals()
item = {"n_first": n_first, "n_nums_to_delete": n_nums_to_delete}

main(item)

Answer 1

You have the answer, sort your results and take the sorted list starting from the n_nums_to_delete :

def get_result(nums, n_nums_to_delete):
    return sorted(nums)[n_nums_to_delete:]

As @Yuri Ginsburg mentioned in the comment, your prime number list is already sorted, so you can simply do :

def get_result(nums, n_nums_to_delete):
    return nums[n_nums_to_delete:]