Почему проходят первые тесты, но не проходят вторые на Codewars?

Question

[SushkaCraftHabr]

Решаю задачи на Codewars. Решил попробовать задачи 5 kyu, дошел до задачи Prime Time.
Ссылка на задачу - https://www.codewars.com/kata/521ef596c106a935c000...
Задача показалась не очень сложной и первое решение написал через 2 минуты. первый тест был пройден, а второй нет(Хотя все отмечено зеленым).
Первый тест -

Второй тест(Пройден, но нет) -


Вот решение -

def prime(n):
    list = []
    for i in range(2, n+1):
        for j in range(2, i):
            if i % j == 0:
                break
        else:
            list.append(i)
    return list

Это второй рабочий вариант, но он тоже не достаточно оптимизирован. Как ещё можно реализовать этот код, но более оптимизированно?

Answer 1

[Vindicar]

Тормозит, потому что ты брутфорсишь перебор простых чисел. Используй решето Эратосфена.
Иными словами, тебе не нужно перебирать все числа меньшие N, чтобы найти делители - достаточно проверить все простые числа, меньшие или равные N/2. А так как ты находишь простые числа по возрастанию, то все эти числа ты уже знаешь.
До кучи, 2 всегда простое, а вот другие чётные числа - нет. Можешь добавить 2 в список заранее, а цикл по i делать от 3 с шагом 2.

Ну и да, не называй переменную list. Это сбивает с толку.