First, I would recommend using an normal array, instead of a collection, which needs more memory, secondly, do you really need to just use ONE sieve? How about 2?

yes, you are indeed missing something, firstly, i don't think your implementation of the sieve is correct, and you should be using the sieve of Eratosthenes, also, you need to think outside the box, as doing the just the sieve is not the intended solution here

i believe you are getting a memory error

you are allowed to use sqrt, what do you mean  you can't?, is it giving you error? 

The memory limit exists for a reason. We will not bump it without extremely good reason to do so, as in my comment from a year ago.

then how do a reduce my memory then?

There are four pages worth of comments. I suggest that you read through them all.

i did, but they didnt help me, help me please jargon

Your program is far too slow. You should also look up the definition of a prime number. Incidentally, adding more p's to your title doesn't make your question more likely to be answered.

Trial division is not fast enough to solve this problem. You'll need to use a different approach; you may wish to read the comments below for some hints.

You're simply using too much memory. You'll need to try a different approach.

However, I've noticed that the memory limit was actually too strict to be solved in Python, which uses references instead of true 1-byte booleans. I also don't think it's fair to force Python users to do some bit hackery just to solve this problem. I've therefore bumped to memory limit from 16M to 32M and confirmed that it's doable.

Thank you very much!

This problem requires a higher level of sophistication than your current solution. There are hints present in comments past.

They're just segfaults:
[code]Traceback (most recent call last):
  File "./a", line 13, in 
    result=[True]*(L-K)
MemoryError[/code]

Traceback (most recent call last): 
  File "./a", line 13, in  
    result=[True]*(L-K) 
MemoryError

A 5 million elements long list of boolean doesn't crash in my computer in either Python 2.6.5 or Python 2.7.2 though, and isn't the maximum difference between N and M is 5 million?

You are correct in that the maximal difference between M and N is 5 000 000. Despite bumping the memory limit up to 128 MiB, your program still gets MemoryError on the last case, and it TLEs on the fourth case.

I don't know enough about Python to give a reasonable explanation as to why you MLE; as for why you TLE, it's likely just because of Python's slow I/O.

Consider trying to solve this in another language.

I only know Python and Visual Basic... crying...

It's possible in python btw. Took a while but got it...

Your solution is practically cheating :P
Congratulations nonetheless on doing this problem in Python.

Can't seem to view this magical source code. Browser can't locate the given URL. And why does your code give the status "OK"?

No repro. I can definitely view this as a non-privileged user. The solution's not that magical anyway :P

OK instead of AC is a relic of days past.