2
\$\begingroup\$

PRIME1 is a codechef problem which states:

Shridhar wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers.

Input

The first line contains t, the number of test cases (less then or equal to 10). Followed by t lines which contain two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output

For every test case print all prime numbers p such that m <= p <= n, one number per line. Separate the answers for each test case by an empty line.

I have optimised my code according to suggestions given here. But, my edits were rolled back when I tried to post my optimised code. So, I am still getting a TLE error and I don't understand why. Help me optimise this code further:

import math
def sieve_basic_list(list_prime):
    max_n=10**9
    m = int(math.sqrt(max_n))
    lim = int(math.sqrt(m))+1
    arr = [True]*(m+1)
    arr[0]=arr[1]=False

    #Calculate primes upto m only so loop runs sqrt(m) times.
    for x in xrange(2,lim):
        if arr[x]==False:
            continue
        for i in xrange(x*x,m+1,x):
            arr[i]=False
    for i,each in enumerate(arr):
        if each:
            list_prime.append(i)

def mnsieve(list_prime):
    #program tc input and mnrange calc
    for _ in xrange(int(raw_input().strip())):
        m,n = map(int,raw_input().split())
        mnrange = [True]*(n-m+1)
        mnrange[0] = False if m==1 else True
        for each in list_prime:
            firstfactor = ((m-1)/each)*each #firstfactor nearest to m i.e firstfactor-m gives index
            for x in xrange(firstfactor,n+1,each):
                try:
                    if x not in list_prime:
                        mnrange[x-m]=False
                except:
                    pass
        for i,each in enumerate(mnrange):
            if each:
                print i+m
        print

list_prime=[]
sieve_basic_list(list_prime)
mnsieve(list_prime)
\$\endgroup\$
  • \$\begingroup\$ I'd recommend you to re-read Janne Karila's third point, as you changed it to something as bad. \$\endgroup\$ – Peilonrayz Apr 5 '17 at 14:56
  • \$\begingroup\$ If you want to keep this approach, at least change list_prime=[] to list_prime=set([]) and list_prime.append(i) to list_prime.add(i). That alone will give you quite the speed improvement. I'd consider re-writing it, though. \$\endgroup\$ – ChatterOne Apr 5 '17 at 15:08
  • \$\begingroup\$ @Peilonrayz Why so? I'm no longer removing an element by searching and then shifting the rest because I don't use remove() anymore. \$\endgroup\$ – mradul dubey Apr 5 '17 at 19:48
0
\$\begingroup\$

Finally, I solved the problem. And these suggestions helped. Here is the final solution:

import math
def sieve_basic_list(list_prime):
    max_n=10**9
    m = int(math.sqrt(max_n))
    lim = int(math.sqrt(m))+1
    arr = [True]*(m+1)
    arr[0]=arr[1]=False

    #Calculate primes upto m only so loop runs sqrt(m) times.
    for x in xrange(2,lim):
        if arr[x]==False:
            continue
        for i in xrange(x*x,m+1,x):
            arr[i]=False
    for i,each in enumerate(arr):
        if each:
            list_prime.add(i)

def mnsieve(list_prime):
    #program tc input and mnrange calc
    for _ in xrange(int(raw_input().strip())):
        m,n = map(int,raw_input().split())
        mnrange = [True]*(n-m+1)
        mnrange[0] = False if m==1 else True
        for each in list_prime:
            if each <= int(n**0.5): #important optmisation
                firstfactor = ((m-1)/each)*each #firstfactor nearest to m i.e firstfactor-m gives index
                for x in xrange(firstfactor,n+1,each):
                        if x!=each and x-m >= 0: #x-m can become -ve and that is disastorous in python lists!
                            mnrange[x-m]=False
       for i,each in enumerate(mnrange):
            if each:
                print i+m
       print

list_prime=set([]) #important optimisation
sieve_basic_list(list_prime)
mnsieve(list_prime)

Check it here: on codechef

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.