views:

84

answers:

1

Hi ,the URL of the problem is ( https://www.spoj.pl/problems/PRIME1/) yeah i did go through some thread about having time limit exceeded. I am using Python 2.6.4 . IDLE . The code is here :

def prime(a):
    count=0
    for i in range(2,int(math.sqrt(a))):
        if(a%i==0):
            count=count+1
    if(count==0):
        return 1
    else:
        return 0
import math
MIN=32000

k=0
list_main=[]
for i in range(MIN):
    list_main.append(1)

for i in range(2,MIN+1):
    if(prime(i)==1):
        k=2
        num=k*i
        while(num<MIN):
            list_main[num]=0
            k=k+1
            num=k*i

test=input()
for i in range(test):


    line=raw_input()
    line=line.split(' ')
    if(len(line)<2):
        print ' 2 integers expected'
        exit()
    try:
        num1=int(line[0])
        num2=int(line[1])
    except:
        print 'integers expected'
        exit()
    list_sec=[]
    for i in range(num2-num1):
        list_sec.append(1)

    num1_s=int(math.sqrt(num1))
    num2_s=int(math.sqrt(num2))
    for i in range(2,num1_s+1):
        if(list_main[i]==1):
            k=2
            num=k*i;
            while(num<num1):
                k=k+1
                num=k*i                
            while(num>=num1 and num<num2):
                list_sec[num-num1]=0
                k=k+1
                num=k*i
    for i in range(num2-num1):
        if(list_sec[i]==1):
            print num1+i

I had earlier mentioned that the program was giving NZEC error. Now i think that may have been the case due to a memory overflow problem( its a guess) . After sorting that out, i am now getting a time limit exceeded error :(

Thanks

A: 

I guess this thread is the one you were referring to.

If I were you I would install Python 2.5 or 3.1.2 on my own machine and try compiling the code locally.

LarsH
Hey, sorry for the late reply. I did install 3.1.2 locally and got a compilation error. But i have edited the question now. Its giving a time limit exceeded error now. Time to go back and tweak the algo :)
crazyaboutliv