SPOJ - liczby pierwsze

Question

Cześć, mam następujący problem, otóż w kodzie do zdania SPOJ (PRIME_T):

i = 0
n = int(input())
podana = []
for i in range(n):
    podana1 = int(input())
    podana = podana + [podana1]

i = 0
for i in range(len(podana)):
    
    czyPierwsza(podana[i])

kod funkcja czyPierwsza nic nie zwraca, tylko pisze "TAK" albo "NIE"

gdy wysyła do sprawdzenia to kod przekracza limit czasu,

czy ktoś miałby jakiś pomysł czemu tak się dzieje?

Comments

Umieściłeś tylko fragment kodu!

---

@lukaskrol7, Nie pokazałeś funkcji czyPierwsza i tam pewnie jest problem. Podejrzewam, że sprawdzasz dzielniki w zakresie (2, n) lub (2, n/2), a wystarczy do pierwiastka n (2, int(sqrt(n)) + 1)

 

---

Dodatkowo (bo algorytm jest najważniejszy)...

W jakim celu wczytujesz dane do listy? Wystarczy wczytać 1 wartość i odpowiedzieć. To także opóźnia obsługę i wpływa na odrzucenie wyniku. Inną sprawą jest także mało wydajna obsługa wczytywania. Dane czytaj z sys.stdin

---

@tangarr, 

nie chciałem wylecieć za wysłanie całego część zapisałem do osobnej funkcji...

def czyPierwsza(liczba):
    dzielniki = 0

    for i in range (liczba-1, 1, -1):
        if liczba%i == 0:
            dzielniki = dzielniki + 1

    if dzielniki == 0 and liczba !=1:
        print("TAK")
    else:
        print("NIE")



i = 0
n = int(input())
podana = []
for i in range(n):
    podana1 = int(input())
    podana = podana + [podana1]

i = 0
for i in range(len(podana)):
    
    czyPierwsza(podana[i])
    

oto cały

---

Powinieneś kończyć po znalezieniu jednego dzielnika, jak znajdziesz jeden to nie ma sensu szukać kolejnych :)

---

faktycznie, bardzo ci dziękuję

---

@reaktywny, 

import sys


n = int(sys.stdin.readline())               
i = 0
for i in range (n):
    podana = int(sys.stdin.readline()) 
    dzielnik = podana - 1
    if podana == 1:
        print("NIE")
        continue
    elif podana == 2:
        print("TAK")
        continue
    while dzielnik>0:
        
        if podana%dzielnik == 0:
            print("NIE")
            break
        dzielnik = dzielnik - 1
        if dzielnik==1:
            print("TAK")
            break

nadal jednak przekracza czas

---

kretiku napisał, że nie musisz sprawdzać wszystkich liczb, z całego zakresu, tylko od 2 do pierw(n)+1.

Masz kilka błędów logicznych w kodzie. Ale więcej się nauczysz, jak je sam poprawisz :)

Answer 1

for i in range(2, int(n ** 0.5) + 1)

n ** 0.5 to to samo co pierwiastek kwardatowy z n

no i jak relatywny napisał wychodzić z pętli po znalizieniu pierwszego dzielnika