SPOJ: Prime Generator

[riveryu]

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

[Shah-Cuber]

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]

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]

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]

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]

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]

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

[saltpro15]

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

[Shah-Cuber]

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]

@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]

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]

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]

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++??