Hello,
I tried the challenge with the prime generator. I program the sieve of eratosthenes and even if I get great improvment in time, I still get the time exceeded error … Any advice ?
this is my code
def compute_prime(n_test, *listofintervals):
for i in listofintervals:
sqrt_max = int(math.sqrt(i[1]))
int_2sqrtp = range(2,sqrt_max+1)
int_np = range(i[0],i[1]+1)
min_2sqrt = int_2sqrtp[0]
min_val = int_2sqrtp[0]
min_val = (min(int_np)/min_2sqrt)*min_2sqrt
if( min_val == 0): min_val = min_2sqrt*2
#while(min_2sqrt*min_2sqrt <= int_np[-1]): #max(int_np)
while( int_2sqrtp ):
#mult_np = range(min_val, max(int_np)+1, min_2sqrt)
mult_np = range(min_val, int_np[-1]+1, min_2sqrt)
mult_2sqrtp = range(min_2sqrt*2, sqrt_max+1, min_2sqrt)
int_2sqrtp.remove(min_2sqrt)
int_2sqrtp = list(set(int_2sqrtp) - set(mult_2sqrtp))
int_np = list(set(int_np) - set(mult_np))
#int_2sqrtp.sort()
int_np.sort()
if( int_2sqrtp ): min_2sqrt = int_2sqrtp[0]
min_val = (min(int_np)/min_2sqrt)*min_2sqrt
if( min_val == 0 ): min_val = min_2sqrt*2
if(int_np[0] == 1):
int_np.remove(1)
#int_np.sort()
print "\n".join([str(x) for x in int_np])
print('')
n_test = int(raw_input())
intervals = numpy.array( [[0,0] for x in xrange(n_test)] )
for i in range(0,n_test):
line = raw_input()
tmp = line.replace('\n','').split(' ')
intervals[i,0] = int(tmp[0])
intervals[i,1] = int(tmp[1])
compute_prime(n_test, *intervals)
Thanks for help =)