Dlaczego SPOJ tego nie akceptuje

Question

Cześć napisałem program w pytonie odnośnie liczb pierwszych który działa dokładnie tak jak opisuje go zadanie jednak mimo to spoj nie akceptuje mojego kodu ktoś wie dlaczego  

kod:

def czypierwsza(x):
    for i in range(2, x):
        if x % i == 0:
            return False
        else:
            return True


a = input()
a = int(a)
lista = []
for o in range(a):
    f = input()
    f = int(f)
    if czypierwsza(f):
        z = "TAK"
        lista.append(z)
    else:
        y = "NIE"
        lista.append(y)

for u in range(a):
    print(lista[u])

Answer 1

Kilka rzeczy

1 - W funkcji czy pierwsza jest błąd, sprawdzasz czy N jest podzielne przez i, jak tak to spoko, że zwracasz false, ale dlaczego jak nie jest to zwraczasz false?

2 - Nawet jak poprawisz tą funkcję czy pierwsza, to i tak moim zdaniem może nie przejść czasowo. To zadanie to chyba chodzi o zaimplementowanie sita Eratostenesa i w O(1) odpowiadanie czy jest pierwsza.

Comments

samo sito Eratostenesa jest dość prostym algorytmem. Dla każdej liczby pierwszej wykreślasz jej wielokrotności, bo one napewno nie będą liczbami pierwszymi.

---

2. Rozwiązanie bez sita powinno zmieścić się w limicie czasowym.

---

Zależy, raczej tak, ale 10^7 operacji może być na styk. Zależy jakie limity.

---

Jeżeli autor poprawi funkcję to powinien osiągnąć ~0.5s (limit wynosi 5).

---

a no to tak jak jest 5 sekund to w C++ powinno wejść(99,9999999999....%). Nie sprawdzałem jakie są limity czasowe. Na pythonie się nie znam, więc nwm w ile się wykona 10^7 operacji.

Answer 2

który działa dokładnie tak jak opisuje go zadanie

no, nie :)

Odpal sobie funkcję `czypierwsza()` na liczbach między 1 a 20 i zobacz czy wyniki są poprawne.

(przy okazji, nie potrzebujesz tej pośredniej listy)