SPOJ Liczby pierwsze - limit czasu

Question

Witam,

Zacząłem uczyć się Pythona, w ramach ćwiczeń przerabiam programy z c++ na python, niestety na Spoju dostałem monit o przekroczonym limicie czasu.

Można tutaj coś usprawnić?

python : https://ideone.com/gxu2CA

Comments

na Spoju

Z tego co pamiętam, limity zasobów (i rankingi) na SPOJu są niezależne od języka programowania i często bywają nacelowane na rozwiązania w C, C++ie i inne języki niższego poziomu. Może się zdarzyć, że ten sam algorytm napisany w C++ie przejdzie, a w Pythonie nie. (dlatego nie lubię SPOJa)

Natomiast faktem jest, że rozwiązanie można jeszcze zoptymalizować - patrz inne odpowiedzi.

Answer 1

Żeby sprawdzić czy liczba n jest pierwsza wystarczy sprawdzić czy dzieli się przez którąś z liczb [2, sqrt(n)]. Jeśli testów jest sporo to można też zaimplementować Sito Eratostenesa.