Primes... again

Given two integers N and M (N ≤ M), output all the prime numbers between N and M inclusive, one per line.

N and M will be positive integers less than or equal to 1,000,000,000.
The difference between N and M will be less than or equal to 5,000,000.

`5 20`

Sample Output

```5
7
11
13
17
19```

Point Value: 15 (partial)
Time Limit: 5.00s
Memory Limit: 32M

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

• (1/1)
why am i not allowed to use #include <math.h> and sqrt(); function in this exercise?

• (1/0)
you are allowed to use sqrt, what do you mean you can't?, is it giving you error?

• (0/1)
Every time i used the sqrt() function, my code would work perfectly, but i somehow got 0 points.so i had to solve the problem a different way.

• (0/0)
Try using to #include<algorithm> and #include<math.h> and then try c++03 and c++11, on the language select section, hope this helps, it doesn;t matter anyways, the way that you were using sqrt was too slow anyways, but good job on doing the problem!

• (0/0)
i'm keeping getting mle on my test cases, can someone bump it up? plz

• (0/0)
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.

• (1/0)
then how do a reduce my memory then?

• (0/0)
There are four pages worth of comments. I suggest that you read through them all.

• (1/0)
i did, but they didnt help me, help me please jargon

• (0/0)
Whats wrong with my code. I tried it so many times.

• (3/0)
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.

• (0/0)
I made a java program that does this but when i submitted it i got a TLE for the last 2 ones.
I'm using trial division up to half of the number

• (0/0)
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.

• (1/0)
May I know why my code is RE for test cases 4 & 5?

• (2/0)
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.

• (1/0)
Thank you very much!

• (0/0)
whats wrong with my submition? pls help

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

• (0/0)
Can you let me know what am I doing wrong for my very last try? I got IR for case 4 and case 5, and I want to know the detail of the invalid return. Thanks a lot

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

• (0/0)
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?

• (0/0)
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.

• (1/0)
I only know Python and Visual Basic... crying...

• (0/0)
It's possible in python btw. Took a while but got it...

• (1/0)
Your solution is practically cheating :P
Congratulations nonetheless on doing this problem in Python.

• (0/0)
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"?

• (0/0)
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.

• (0/3)
My code still not working

• (0/0)
``ValueError: invalid literal for int() with base 10: '5 20'``

• (1/0)
I took down the forums because nobody seemed interested in using them.

• (1/0)

• (0/0)

• (1/0)
I still don't get it.

• (0/0)
I would recommend leaving this problem for later on, after you've had a chance to work on some more difficult problems.

If you're adamant about trying this (good on you! determination is important), I wrote a hint comment a while ago.

• (0/0)
I am getting runtime error in the last two test cases but I don't really care about that.Would any of the admin confirm correctness of my algorithm for first three test cases.I think I just had blindshot for first three test cases.Would anybody care to check my algorithm.Thanks :)

• (0/0)
I guess your idea to compress the sieve with a set is smart. Unfortunately this won't work for this problem since you're still creating an awfully large amount of integers when you are executing your sieve(enough to cause an MLE). I suggest that you read the hints below and think of a smart way to sieve within the range specified.

• (1/0)
I tried using Sieve of Eratosthenes in Java but got an MLE for the last test case. On your wiki it says MLE is usually caused by a large array, which is what I used. How else could I approach this. Thanks.

• (2/0)
It is possible to consider a much smaller set of numbers than the entire 1,000,000,000 range. There's a certain optimization to be made to your sieve that might make this mathematically clear.