Как ускорить (оптимизировать) код на Python?

Question

[Антон Винокуров]

Доброго времени суток! Уважаемые программисты, помогите оптимизировать код на Python (простите за глупую просьбу, просто я чайник)

def IsPrime(n):
    d=2
    while d * d <=n and n%d!=0:
        d +=1
    return d * d>n
def list_prime(n):
    return [i for i in range (2,n+1) if IsPrime (i)]
n = int(input())
lst= list_prime(n)
for num in lst:
    x = n-num
    if x in lst:
        print(f"{num}+{x}")
        break
    
print()

Кому интересно, вот задача:
Дано целое число n. Предоставьте его в виде суммы простых чисел.
Если есть k слагаемых, то ответ должен быть в формате "a1+a2+...+ak"(без пробелов). Среди всех таких рядов ваш ответ должен быть лексикографически минимальным.
Ряд a считается лексикографически меньше за ряд b, если используется хотя бы одно условие:
1) a - b префикс , но длина b больше за длину a, например, ряд "abc" есть лексикографически меньше за "abcd"
2)есть такая позиция p , что a1 =b1, a2=b2, ..., ap-1=bp-1, a также ap Символ "+" лексикографически меньше за символы цифр 
Формат входных данных
Первый ряд имеет одно целое число n (2= Формат исходящих данных
Вывести ответ на задачу

Comments

[alfss]

что-то мне кажется, что этой биржей лучше не пользоваться, там описание АПИ швах, код их швах.

Answer 1

[o5a]

1. По поводу самого алгоритма поиска простых - есть более эффективный, Решето Эратосфена, в базовом исполнении он достаточно простой, приводить не буду, легко находится поиском. Это на случай, если действительно упирается в скорость.

2. Вывести строку в виде a1+a2+... можно с помощью join()
print("+".join(lst))

3. Требование лексикографически минимального результата написано не до конца понятно, предположу, что достаточно вывести с отсортированными лексикографическими (т.е. по строке) значениями, т.е. просто сортируем наш список простых чисел по их строковым значениям, например так (map используется для перевода цифровых значений нашего списка в строковые):

print('+'.join(sorted(map(str, lst))))