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)

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

is there a way to make arrays 1 trillion size o.0?

The memory limit on this problem is 16 MB, which is around 4 million ints, 8 million shorts, or 16 million chars/bools. Standard compilers won't let you declare arrays larger than about 2 GB, but you don't get that much memory anyways.

i wonder who scott...i wonder who...

BTW, I submitted 15 times, and 10 of those times were just me being stupid, and finding out the test data.

I sumbitted A+B(2) like 40 times -_-

What is this??? Only 20 points for this problem, that's unbelievable. Only 2 out of 162 submissions were correct. TWO OUT OF 165!!! Which were Jacob and Hanson anyways. That's ridiculous, they each have over 3000 points (this tells you just how good they are) and for a problem only they can solve, you get 20 points. Come on! Why would anyone do this problem when they can do 4 five pointers in one tenth the time (and at least youd get the 5 pointers right). I'm just saying, the point system is messed, these harder problems deserve a lot more points because 1. They take 10 times as long, and 2. Only a few can even hope of finishing them.

YOU TELL EM ANDREW!! from the land of the bernesh

who cares, just forget the points for a moment and think of the learning experience you go through to solve this problem (or when you get some help on it :P). anyhow, Hanson, Jacob and co. need much higher scores than us in comp sci, so they should be getting points from as many sources as possible (and doing these problems over and over again is what keeps their brains thinking).

Although this problem is an exception, the point system is quite valid.

The more you are used to a certain level, the easier it is to do the questions of that level.
I know people who thought they are only capable of doing 3pt questions, the 5pt questions were hard and would take a long long time. They thought it was rigged but after a while, they did more and more 5pts and they got used to it. Now as they think back, the 5pt, weren't so hard after all. Same applies for 10pt. Same applies to this.

that the last test case (which i'm TLEing on) is

995 000 000
1 000 000 000

How many points are you willing to bet?

in that case, i win and lose, so the net gain would be 0.

The last test case is not quite what you stated.