Computer Science Canada

SPOJ: Prime Generator

Author:  riveryu [ Fri Sep 04, 2009 11:09 am ]
Post subject:  SPOJ: Prime Generator

Hi guys, I just signed up for SPOJ and I started doing the problems. The second one I'm doing is Prime Generator (PRIME1).

At first I tried a probabilistic primality test using Fermat's Lesser Theorem and a theorem related to quadratic probing. It timed out on my own laptop. Then I tried Miller-Rabin, it was slow and gave me wrong answers sometimes. I'm working on an optimized segmented sieve of Eratosthenes right now, it should work for that problem but I want to learn more. I'm having some trouble finding good material on this kind of stuff. Even google fails me.

Does anyone know any sites that has plain English description about prime test/sieve algorithms? (I'm too poor/cheap/lazy to get books)
I already went through 5 google search pages at least.

Yes, I know about Wikipedia, its too short and technical (I have to DFS the links to words I don't know on each page and it gets annoying).

Author:  Shah-Cuber [ Fri Sep 04, 2009 11:28 am ]
Post subject:  Re: SPOJ: Prime Generator

PRIME1 is kinda tricky at the beginning, but the solution I had was simple:
Use sieve for all values, and check if each value is a prime or not (boolean)
Then just divide the input into two parts, before 10^6 and after 10^6, and you could have a separate algorithm for input of 999900000 - 1000000000 (worst case scenario)
also, Miller-Rabin is too slow for this, try using C/C++, i began with Java/python ... but it was too slow, certainly not O(log n) ...
I also recommend this article(below) for a fast implementation of sieve of Eratosthenes(segmented), which for any prime numbers in the subinterval [P,Q], which according to them can result in A (Q-P) log(log(Q))+B pi(sqrt(Q)) time, but if you just don't want to learn that, just search it on wolfram mathworld Smile
Hope that helps ...

Link to article:

Author:  Analysis Mode [ Fri Sep 04, 2009 3:49 pm ]
Post subject:  RE:SPOJ: Prime Generator

I didn't look at that link, but you don't need any h4x sieve implementations.

Here's a hint: You don't sieve the entire 1..1000000000. Sieve part of it and use the information obtained in a cleverer way.

Author:  saltpro15 [ Fri Sep 04, 2009 9:41 pm ]
Post subject:  RE:SPOJ: Prime Generator

you are attempting to use a laser guided nuclear bomb to squash a fly Very Happy There is a much simpler way to do this as Shah-Cuber and Analysis Mode have already hinted

Author:  A.J [ Fri Sep 04, 2009 9:46 pm ]
Post subject:  RE:SPOJ: Prime Generator

I believe the saying is 'using a sledge hammer to kill a fly', but it conveys the same message.

I too believe that overlooking the obvious is an all too common mistake in this question.

Author:  riveryu [ Fri Sep 04, 2009 10:33 pm ]
Post subject:  Re: SPOJ: Prime Generator

Well I could be killing a fly right now, but I want to to know more about my sledge hammer since the best solution ran at 0.00 sec and I want to beat it now. If only I can see how long his code was.

Thanks, but I already thought of the workable solution.
Basically, sieve up to sqrt(n) + 1 first, and then sieve m <-> n.

@Analysis Mode
I looked at that site and his source code (which was > 400 lines) but can't understand his "improvements".
However, I did try to do some pre-sieving, tying to make my algorithm completely ignore numbers divisible 2,3,5 described on another site. This makes the numbers to be considered to be decreased by a factor of ~3.75.

Author:  riveryu [ Sat Sep 05, 2009 1:51 pm ]
Post subject:  Re: SPOJ: Prime Generator

I made my short version of sieve of erasto. SPOJ gave me "wrong answer" and I can't figure out why. Someone help?
I'm new to C++, and I had to a lot of review to write this question in C++.
Don't tell me its one of output format mistakes...

Author:  saltpro15 [ Sat Sep 05, 2009 2:37 pm ]
Post subject:  RE:SPOJ: Prime Generator

SPOJ has a forum too, but I'll take a look

Author:  Shah-Cuber [ Sat Sep 05, 2009 3:03 pm ]
Post subject:  Re: SPOJ: Prime Generator

It only took me a minute till I found a wrong answer: if you put in the input; 1 2 10, your program outputs 3 5 7, when it's suppose to be 2 3 5 7 (inclusive), I think you can figure out your problem yourself =P
Also, i don't think your sieve is efficient enough for this ...

Edit: On an unrelated note, are you the same River from A.Y.J?

Author:  riveryu [ Sat Sep 05, 2009 4:31 pm ]
Post subject:  RE:SPOJ: Prime Generator

Ok I fixed that and it was stupid mistake of reusing variables. And yea I am. Also, this code ran 999900000-1000000000 instantly on laptop at least.

I fixed the mistake and submitted again, wrong answer again...

Author:  Cyril [ Tue Sep 08, 2009 9:28 pm ]
Post subject:  RE:SPOJ: Prime Generator

I think deterministic Miller-Rabin is quite feasible for this. Just use witnesses 2, 7, and 61. Considering that Python has a built-in pow(a,b,m), which computes a^b mod m with binary exponentiation... you can afford to be quite lazy.

Of course, being noble, I implemented the double sieve method first. (my first lazy Miller-Rabin attempt got WA, so I gave up.)

Author:  A.J [ Tue Sep 08, 2009 9:43 pm ]
Post subject:  RE:SPOJ: Prime Generator

Nice to have you back, Cyril. And I believe that Miller-Rabin is actually useful, and is good practice. Having said that, I don't think that it is the only method of solving this problem (as Cyril stated)

Author:  naivecoder [ Fri Jan 13, 2012 12:19 am ]
Post subject:  RE:SPOJ: Prime Generator

hey cyril....
u r saying this prime generator problem can be done through miller-rabin...
miller-rabin:- a^d mod N=1 ..ok?
what if a=61 and d is selected as 99999
given that one is using C or C++??