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


All Submissions
Best Solutions

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

Problem Types: [Show]

Languages Allowed:

Comments (Search)


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

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.

My code still not working

ValueError: invalid literal for int() with base 10: '5 20'

I took down the forums because nobody seemed interested in using them.

Yes, same thing with me except I keep on getting 25/100. Please help!

Your naive algorithm is too slow. Read the below comments for hints.

I still don't get it.

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.

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 :)

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.

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.

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.

I tried using Sieve of Eratosthenes but I cannot seem to find the error in this program... I understand it's harder in python but does anyone know what exactly is causing the errors? Thanks :)

N and M are at most 1,000,000,000. Any large test cases around that size will require way too much memory to store and there's no way you'll ever be able to do it like that. This problem is worth 15 points, which is a lot more than the average prime problem. This is due to the fact that this cannot be done using the naive way, and you would have to chance your algorithm a bit.

I'm getting runtime error.
Does this mean that I timed out? What does it mean?
(It would be helpful if I could see the error message)

Try resubmitting. You should be able to see what kind of runtime error it is now.

i know how to do this but the largest ordinal thing is longint...

Couldn't you also use Int64? and why would you need anything that large anyways?

what is SIGSEGV?

You may want to read the 'help' section.