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)


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.

The time limit per case has been increased to 5 seconds so that Java users can solve this problem.

In other languages, any solution that times out with 2 seconds will still time out with 5 seconds.

Can't you have a language specific time limit? E.g. slower langs like Java and anything interpreted could have a different time limit for problems (say 1.5x or something). This would also avoid having to manually redo all the other problems impossible to do in time limit which invariably exist.

No, it would just be far too much trouble. If we increase the time limits by a factor of 1.5 for Java, what should the factor be for Python? PHP? Ruby? Perl?

In my opinion, if you're not using a language that uses almost every machine instruction doing calculations (C, C++, Pascal, assembly) then you're already doing something wrong.

I applied a variation of sieve of Eratosthenes. It takes approximately 3.9 seconds on the last case ? How can I make it faster ?

A hint I can give is to try to combine your init() procedure with your main program. Output optimisations are not required in this problem.

I am sorry I don't get it. I mean, did everyone use Sieve of Eratosthenes or something else. Like How do I integrate init( ) with the program ?

Yeah, from just a quick glance, every accepted submission makes use of the Sieve of Eratosthenes.

As Daniel said, with the right idea, output optimisation is unnecessary and over-complicates your code.

Here's a hint: If you know all the primes up to some number M, you can determine all the primes up to some number N. How are M and N related? (Yes, your code implies you already know this; you're just not applying it in the best way.)

Thanks to Daniel and jargon.Accepted.

So first you use the sieve of Eratosthenes and then...?

The Sieve of Eratosthenes finds prime numbers. So I'm not sure what you mean by "and then"... all you do is print the prime numbers you find. You do need to implement a variation on the standard Sieve though, otherwise you'll need a boolean array of size one billion and your program will run out of time anyway. Once you figure out what that variation is, the problem should be easy. If you're stuck, try solving other problems and then coming back to this one later.

Well, can you give me a clue on the variation?
Is it, a), an integer,
b) string,
c) char?
An array as well, right?

I recommend that you try this problem later when you have more coding experience. You should at least try coding the original Sieve, anyway, and see whether you can get Primes (1) accepted.

Can't you use an array of [1..5000000] of boolean for this question instead?

Yes, you should. This is not necessarily the only array you need to use, though.

You can use an array like that, it's just small enough to fit into the memory allowance. However, not just any solution will run in time.