SPOJ: Prime Generator
Author 
Message 
riveryu

Posted: 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 MillerRabin, 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).






Sponsor Sponsor



ShahCuber

Posted: 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, MillerRabin 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 (QP) log(log(Q))+B pi(sqrt(Q)) time, but if you just don't want to learn that, just search it on wolfram mathworld
Hope that helps ...
Link to article: http://www.ieeta.pt/~tos/software/prime_sieve.html






Analysis Mode

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






saltpro15

Posted: 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 There is a much simpler way to do this as ShahCuber and Analysis Mode have already hinted






A.J

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






riveryu

Posted: 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.
@ShahCuber
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 presieving, 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.






riveryu

Posted: 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...
Description: 

Download 
Filename: 
prime4.cpp 
Filesize: 
1.79 KB 
Downloaded: 
899 Time(s) 






saltpro15

Posted: Sat Sep 05, 2009 2:37 pm Post subject: RE:SPOJ: Prime Generator 


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






Sponsor Sponsor



ShahCuber

Posted: 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?






riveryu

Posted: Sat Sep 05, 2009 4:31 pm Post subject: RE:SPOJ: Prime Generator 


@ShahCuber
Ok I fixed that and it was stupid mistake of reusing variables. And yea I am. Also, this code ran 9999000001000000000 instantly on laptop at least.
I fixed the mistake and submitted again, wrong answer again...






Cyril

Posted: Tue Sep 08, 2009 9:28 pm Post subject: RE:SPOJ: Prime Generator 


I think deterministic MillerRabin is quite feasible for this. Just use witnesses 2, 7, and 61. Considering that Python has a builtin 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 MillerRabin attempt got WA, so I gave up.)






A.J

Posted: Tue Sep 08, 2009 9:43 pm Post subject: RE:SPOJ: Prime Generator 


Nice to have you back, Cyril. And I believe that MillerRabin 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)






naivecoder

Posted: 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 millerrabin...
millerrabin: a^d mod N=1 ..ok?
what if a=61 and d is selected as 99999
given that one is using C or C++??







