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 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).
|
|
|
|
|
|
Sponsor Sponsor
|
|
|
Shah-Cuber
|
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, 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
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 Shah-Cuber 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.
@Shah-Cuber
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.
|
|
|
|
|
|
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: |
914 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
|
|
|
Shah-Cuber
|
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 |
|
|
@Shah-Cuber
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...
|
|
|
|
|
|
Cyril
|
Posted: 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.)
|
|
|
|
|
|
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 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)
|
|
|
|
|
|
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 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++??
|
|
|
|
|
|
|
|