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)

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.

Anyone know why you can't set an array of 5000000 bools in MinGW on Code::Blocks 10.05? Gives general SIGSEGV fault, but works fine on judge.
Is it a Windows limitation? I thought I could create arrays of 5MB on Free Pascal...

That's because memory on the stack is limited. There's much more on the heap.
On windows, you could try (assuming mingw uses gnu gcc compiler )
Go to CodeBlocks->Settings->Compiler and Debugger->Linker settings->Other linker options and add
"--stack,16777216" (no quotes) to increase stack size to 16MB (or use any other reasonable value)
Then your code should work, unless you want 20 million booleans.


not that stack size is different from the total memory available to the program
(you probably have at least a gigabyte of memory available on your own computer.)

Or you could've just written your program in one of the following ways.

Make a global boolean array of size 5 million

or
#include <vector>
...
vector<bool> isPrime (5000000); //(may cause frustration in some cases)
or
bool*isPrime = new bool[5000000];
...
delete []isPrime;

I am getting runtime error. Is it because I am exceeding the memory limit.

Yeah, executing your program on the terminal gives
"terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
Aborted"
However, even when the memory limitation is removed, it TLEs.

there is a "well-known" algorithm for generating prime numbers up to N, as Dr. Sane pointed out. Try finding it.

What is the largest array possible for this program without exceeding the memory limit?

You can do the math yourself.

The memory limit is 16MB - that's 16,777,216 bytes.
A boolean is 1 byte, an integer is 2 bytes, and a longint is 4 bytes.


In your case it means memory access out of bounds.
What happens in your code if M or N is greater than 5000000?


In your particular case it means you are using too much memory.

but the judge says that i'm only using 64kb of memory for that one

The memory reading is often inaccurate, and also since your attempt at allocating a huge array fails, the memory usage doesn't include the size of that array anyways.