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)

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
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.

The judge's accuracy is roughly +/-0.004s - if you want a faster runtime, optimize your program.
Hint: cin and cout are rather slow.

What can you replace cin or cout with?

scanf and printf

Didn't SourSpinach exceed time limit?

no it's 2 seconds per test case, so my program could thereotically take 10 seconds. however, I can't take 3 secs on 1 test case and 1 on another.

It's only difficult if you don't know of the "well known" algorithm for generating primes. It's really quite straight forward once you do, and maybe even unfair for those who don't. (Is a hint perhaps justified?) But that being said, you can still hack it as SourSpinach did.

Actually, looking at Sour Spinach's code, he still used the same algorithm. But not in the same way as the rest of us.

is that dissension i am hearing?

¿Cómo? Did you mean "dissent"?

the program isnt that hard if you really think about it so stop complaining.

then why do you only have 3/20...