Przekroczono limit czasu

0

Cześć zaczynam swoją przygodę z Pythonem , mam takie zadanie https://pl.spoj.com/problems/PRIME_T/ i taki kod :

standard_input = int(input(""))
for i in range(0, standard_input, +1):
    number = int(input(""))

    if number==1:
        print("NIE\n")
    elif number==2:
        print("TAK\n")
    l=2
    for x in range(l,number,+l):
        if number%x==0:
            print("NIE\n")

        elif x==number-1:
            print("TAK\n")

błąd który wyskakuje brzmi przekroczony limit czasu sądze że błąd jest w linijcie for x in range(l,number,+l): za pomoc z góry dziękuje

Dobra ogarnołem że nie mam n - liczba testów n<100000, w kolejnych liniach n liczb z przedziału [1..10000]

0
  1. Twój program jest nieprawidłowy https://ideone.com/iixqEL
  2. Twój algorytm (po poprawce) ma zbyt dużą złożoność czasową (jest zbyt powolny).
0

Jest to sprawdzenie bardzo naiwne, można spróbować troszkę lepsze:

def is_prime(n):
	if n <= 3:
		return n > 1
	elif n % 3 == 0 or n % 2 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % i + 2 == 0:
			return False
		i += 6
	return True
0

Nawet jeśli zadania wyglądają na proste, to na spoju zazwyczaj należy w nich zastosować algorytmy, których implementacja nie jest oczywista bez odpowiednich twierdzeń/teorii.

0

Oto przykładowe, szybkie rozwiązanie:

import base64, zlib, itertools

p=set(itertools.accumulate([2]+eval(zlib.decompress(base64.b85decode(b'c${@sTaM&F2)j@|3Q|JcWwrOe#w1_^mC<NtTir>8hiy#$$)(S~UH|R*wEEt^EPneqDI3RS#eJ(M;=+4K;;#cgH|&V|T!=7;XMFU{WFx2N4P=^?Jn{2DJpJ|}o^hCGe6^}-jRu7opR4%DqmIw0?JZT0=FZvy%wn~U_<$)p5<M}SU5Q@}dzPR`=xo9n0j*^f{)@S&)UKPs#E)_bpA9UO2nM1uarVhJ6TOcuB-CAqRK-cO_yKyxw&Z#bAeE=}y{&KOc6lB0fmLz=vX8WfuA*t(q}C9pz9hx*U?gM1Rhkiy!D7@Ow+)zj0is%Ect*}jXSxsgi=`e4LkpEOGd}623>Fel4C+U$O%AEJg>3eg4nhC`N!9`s;jCs5L(&5fFp44aGzKmC)R1+rI$5-<2VII!+!%uhdMIGZr1Z>ho+H#E6-*?V>A}&&IT`@wqSS^};1Ez?-i7P;!rQ{V2APJT<TNR#z|Puh0*VePIJ}F209VBmhe$#a+Cxp2HtI2G#7bHO9Ms6341?F4(P5~tY$q@@N^Q$h2nm`n%K1Hh)AWZGaKb?CriZousl7;cAH%&51Thq0yy1DPFMdq-+bNz(kfOi*?HBn1KqXooo5(5Wwy0fJJC+ZJra^#!jIo16x_zy?dyxn2C+GtTiC9TzZW4~hu1V$HRfa0u#8Q?O;2m4G%qLxf@~Xy-w5yKRF+Rp|KxEpXGy^qb4iE6l2!j3EeUrV<`j%Y}t?RS7t%`oD3VkSe)tZn^84i<A=Hd})kMDV^odUk6c`48s?;2Q_pBEl2kHPsUa5ffu97S<iFF-Smu}!4cb{WcKG)1+Bp)-s!y5-pJS~ay}dOK-z%=w4W5p<pN$90s%uNq_TomH05b9cN?YP+~-y9`&@ZQyw<tv2>7RNH`P#`;&W{Q{d*)!S`AX#alzB*`82')))))
n=int(input())
for _ in range(n):
    print("TAK" if int(input()) in p else "NIE")

1 użytkowników online, w tym zalogowanych: 0, gości: 1