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)

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?

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

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

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.