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.

Sample Input

5 20

Sample Output

5
7
11
13
17
19

All Submissions
Best Solutions


Point Value: 15 (partial)
Time Limit: 5.00s
Memory Limit: 32M
Added: Oct 18, 2008

Problem Types: [Show]

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

Comments (Search)


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?

I'm fairly certain I'm using the algorithm(sieve) properly and have done my best in making my code as efficient and fast as possible.
Am I missing something?

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

Since it truncates the error message, I don't know what error I'm getting. Can anyone paste it by chance? Thanks!

i believe you are getting a memory error

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

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

i'm keeping getting mle on my test cases, can someone bump it up? plz

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

Whats wrong with my code. I tried it so many times.

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.

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

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.

May I know why my code is RE for test cases 4 & 5?

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!

whats wrong with my submition? pls help

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

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

They're just segfaults:
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.